題目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; }