題目3.方格填數(shù)

如下的10個(gè)格子

填入0~9的數(shù)字。要求：連續(xù)的兩個(gè)數(shù)字不能相鄰。

（左右、上下、對(duì)角都算相鄰）

一共有多少種可能的填數(shù)方案？

請(qǐng)?zhí)顚懕硎痉桨笖?shù)目的整數(shù)。

注意：你提交的應(yīng)該是一個(gè)整數(shù)，不要填寫任何多余的內(nèi)容或說明性文字。

數(shù)學(xué)好的可以直接用數(shù)學(xué)推算出來，用組合與計(jì)數(shù)的方法還是可以的。

既然藍(lán)橋杯考驗(yàn)計(jì)算機(jī)編程能力，我這里還是采用算法來做。

這是一道考察dfs算法的題目，首先10個(gè)格子不夠規(guī)范，我們先補(bǔ)成12個(gè)格子(3*4)。

接下來要注意三個(gè)步驟：

①初始化：如何制作表格；如何給每個(gè)格子打上標(biāo)記的問題；

②判斷：判斷點(diǎn)有哪些？

是否在矩陣內(nèi)？該格子是否可用？是左上還是右下的那個(gè)格子不能用？

③DFS搜索：三種情況的討論？

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

DFS算法的注意點(diǎn)：DFS對(duì)某個(gè)格子的數(shù)字搜索完后一定要還原，一定！！！

/*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;		}	}	//左上和右下兩個(gè)格子不能用 	flag[0][0]=0;	flag[2][3]=0;	}void check(){	int temp=1;//檢驗(yàn)該填法是否合法	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];				//移動(dòng)后是否還在矩形內(nèi)？ 				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){//針對(duì)右下最后一個(gè)格子 	//12個(gè)格子全部搜索完畢，dfs結(jié)束 		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{//針對(duì)左上第一個(gè)格子 		dfs(n+1); 	} } int main(){	init();	dfs(0);	cout<<ans<<endl;   return 0; }