题目描述
如下的10个格子，填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）一共有多少种可能的填数方案？
image
输出
请填写表示方案数目的整数。
代码
又是一道dfs题，因为是填空题如果实在想不出可用暴搜
#include<bits/stdc++.h>
using namespace std;
int a[4][5],visit[10];
int dx[4]={-1,-1,-1,0};
int dy[4]={0,1,-1,-1};
int sum;
bool check(int x,int y,int n){
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<3&&xx>=0&&yy>=0&&yy<4){
if(abs(a[xx][yy]-n)==1)
return false;
}
}
return true;
}
void dfs(int x,int y){
if(x==2&&y==3){
sum++;
return;
}
for(int i=0;i<10;i++){
if(visit[i]==0&&check(x,y,i)){
visit[i]=1;
a[x][y]=i;
if(y+1<4)
dfs(x,y+1);
else
dfs(x+1,0);//另起一行
visit[i]=0;
}
}
}
int main(){
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
a[i][j]=-20;
dfs(0,1);
cout<<sum;
return 0;
}
