2016年蓝桥杯C语言大学A组题目3--方格填数

题目3.方格填数

如下的10个格子

填入0~9的数字。要求：连续的两个数字不能相邻。

（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

请填写表示方案数目的整数。

注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

数学好的可以直接用数学推算出来，用组合与计数的方法还是可以的。

既然蓝桥杯考验计算机编程能力，我这里还是采用算法来做。

这是一道考察dfs算法的题目，首先10个格子不够规范，我们先补成12个格子(3*4)。

接下来要注意三个步骤：

①初始化：如何制作表格；如何给每个格子打上标记的问题；

②判断：判断点有哪些？

是否在矩阵内？该格子是否可用？是左上还是右下的那个格子不能用？

③DFS搜索：三种情况的讨论？

左上角？右下角？一般情况？

DFS算法的注意点：DFS对某个格子的数字搜索完后一定要还原，一定！！！

/*name:Rollchuchytype:dfs*/#include<iostream>#include<cstdio>#include<cmath>using namespace std;int row=3,col=4; int map[3][4];int flag[3][4];int vis[10];int dis[8][2]={0,1,//right0,-1,//left1,0,//up-1,0,//dowm1,1,-1,1,1,-1,-1,-1,}; //方向 int ans=0; void init(){	//init   	for(int i=0;i<10;i++){   		vis[i]=0;	   }	for(int i=0;i<row;i++){		for(int j=0;j<col;j++){			map[i][j]=0;			flag[i][j]=1;		}	}	//左上和右下两个格子不能用 	flag[0][0]=0;	flag[2][3]=0;	}void check(){	int temp=1;//检验该填法是否合法	for(int i=0;i<3;i++){		for(int j=0;j<4;j++){			if(flag[i][j]==0) continue;			for(int k=0;k<8;k++){				int x=i+dis[k][0];				int y=j+dis[k][1];				//移动后是否还在矩形内？ 				if(x<0||x>=3||y<0||y>=4||flag[x][y]==0) continue;				if(abs(map[i][j]-map[x][y])==1) temp=0;			}		}	} 	if(temp){		ans++;	}}void dfs(int n){	int x=n/4;//row	int y=n%4;//col	if(x==3){//针对右下最后一个格子 	//12个格子全部搜索完毕，dfs结束 		check();		return ;	}	if(flag[x][y]){		for(int i=0;i<=9;i++){			if(vis[i]==0){				map[x][y]=i;				vis[i]=1;				dfs(n+1); 				vis[i]=0; //注意！一定要还原 			}		}	}	else{//针对左上第一个格子 		dfs(n+1); 	} } int main(){	init();	dfs(0);	cout<<ans<<endl;   return 0; }