本文共 3282 字，大约阅读时间需要 10 分钟。

如下的10个格子

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

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

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

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

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

思路一： 方格以二维模拟

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int ans;bool vis[10];int flag[3][4];int map[3][4];bool check(int x, int y)//对某一个格子判断 	{		int i, j;		for(i = -1; i <= 1; ++i){			for(j = -1; j <= 1; ++j){			//	if(i == 0 && j == 0) continue;				int nx = x+i;				int ny = y+j;				if(!flag[nx][ny]) continue;				if(nx>=0 && nx<3 && ny>=0&&ny<4){					if(abs(map[x][y]-map[nx][ny]) == 1)						return false;					}			}		}		return true;	}	void dfs(int x, int y)	{		if(x == 2 && y == 3){ //到达最后一个格子的下一个位置  判断所有的格子是否都满足条件 			int f = 1;			for(int i = 0; i < 3; ++i){				for(int j = 0; j < 4; ++j){					if(flag[i][j] && !check(i,j)){						f = 0;						break;					}				}			}			if(f){				++ans;			} 			return ;		}		if(flag[x][y]){			for(int i = 0; i < 10; ++i){				if(!vis[i]){					map[x][y] = i;					vis[i] = true;					if(y < 3){						dfs(x,y+1);//如果此行还有格子 					}					else{						dfs(x+1,0);//从下一行第一个开始判断 （这里因为除了第一行外下一行第一个一定有效） 					}					vis[i] = false;				}			}					}	}int main()	{		for(int i = 0; i < 3; ++i){			for(int j = 0; j < 4; ++j){				flag[i][j] = 1;				map[i][j] = 0;			}		}		flag[0][0] = flag[2][3] = 0;//标记无效格子 		dfs(0,1);		cout << ans;		return 0;		}
      
     
    
   

#include
   
    #include
    
     #include
     
      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
      
       =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格子走到12时候12/4 刚好为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<
       
        <
       
      
     
    
   

思路二：

用 全排列 然后 枚举

#include
   
    #include
    
     #include
     
      using namespace std;int a[10];/*1 24 5 68 9*/bool judge(){        if(abs(a[0]-a[1])==1||abs(a[0]-a[5])==1||abs(a[0]-a[4])==1||abs(a[0]-a[3])==1){        return false;    }    if(abs(a[1]-a[2])==1||abs(a[1]-a[6])==1||abs(a[1]-a[5])==1||abs(a[1]-a[4])==1){        return false;    }    if(abs(a[2]-a[6])==1||abs(a[2]-a[5])==1){        return false;    }    if(abs(a[3]-a[4])==1||abs(a[3]-a[8])==1||abs(a[3]-a[7])==1){        return false;    }    if(abs(a[4]-a[5])==1||abs(a[4]-a[9])==1||abs(a[4]-a[8])==1||abs(a[4]-a[7])==1){        return false;    }    if(abs(a[5]-a[6])==1||abs(a[5]-a[9])==1||abs(a[5]-a[8])==1){        return false;    }    if(abs(a[6]-a[9])==1){        return false;    }    if(abs(a[7]-a[8])==1){        return false;    }    if(abs(a[8]-a[9])==1){        return false;    }        return true;}int main(){    int i;    int sum;        for(i=0;i<10;++i){        a[i]=i;    }        sum=0;    do{        if(judge()){            ++sum;        }    }while(next_permutation(a,a+10));        printf("%d\n",sum);        return 0;}