2016年蓝桥杯省赛A组c++第3题(图论)

/*
有一个含有10个格子的图形，现用0~9填充，连续的数不能填充在相邻的格子中（包括对角线相邻）。
现每个数只能填写一次，问有多少种填充方法？
0111
1111
1110 
（1表示有格子，0表示没格子） 

解题思想：深度优先遍历即可
*/ 

#include<cstdio>  
#include<cstring>  
#include<algorithm>  
#include<iostream>  
#include<string>  
#include<vector>  
#include<stack>  
#include<bitset>  
#include<cstdlib>  
#include<cmath>  
#include<set>  
#include<list>  
#include<deque>  
#include<map>  
#include<queue>
using namespace std;

int t;  //t用于存放已经填写了的格子数目 
int flag[10];  //记录数字是否选  
int map[4][5];  //格子表 
int sum=0;  //sum为可行解的数目 

int judge()//判断已经填好的表是否符合要求  
{
int i,j;  
for(i=0;i<3;i++)  
    {  
for(j=0;j<4;j++)  
if(abs(map[i][j]-map[i][j+1])==1/*左右*/||abs(map[i][j]-map[i+1][j])==1/*上下*/||abs(map[i][j]-map[i+1][j-1])==1/*左上角*/||abs(map[i][j]-map[i+1][j+1])/*右上角*/==1)  
return 0;  
    }  
return 1;  
}  

//dfs函数用于填表  
void dfs(int t)  
{
int i;  
if(t==11)//t=11,即此时表中的10个格子全部填了数  
    {  
if(judge())  sum++;
return;  
    }  
for(i=0;i<=9;i++)  
    {  
if(!flag[i])  
        {  
            flag[i]=1;  
            map[t/4][t%4]=i;  
            dfs(t+1);  
            flag[i]=0;  //若递归返回，则说明该解不可行。回溯思想。 
        }  
    }  
}  

int main()  
{  
int i;  
for(i=0;i<4;i++)  
    {  
        map[i][4]=1000;  
    }  
    memset(flag,0,sizeof(flag));  //记号表归零 
for(i=0;i<5;i++)  
        map[3][i]=1000;  //画表格图 
    map[0][0]=map[2][3]=1000;  
    dfs(1);  
    printf("%d\n",sum);  
return 0;  
}

 

 

 

tz@COI HZAU

2018/3/15