本文共 2692 字，大约阅读时间需要 8 分钟。
方格填数如下的10个格子 +--+--+--+ | | | |+--+--+--+--+| | | | |+--+--+--+--+| | | |+--+--+--+（如果显示有问题，也可以参看【图1.jpg】）填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）一共有多少种可能的填数方案？请填写表示方案数目的整数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：
DFS
优化：
因为搜索的位置是按照很纵坐标依次增大来的，所以原来设定的8个方向就可以缩短为4个方向。
测试结果：1580
代码：
#include优化之后：#include #include #include #include using namespace std;int ans[3][4];bool bns[10];int dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};int sum=0;void init(){ memset(ans,-1,sizeof(ans)); memset(bns,false,sizeof(bns));}bool check(int x, int y, int num){ int sx,sy; for(int i=0;i<=7;i++) { sx=x+dir[i][0]; sy=y+dir[i][1]; if(sx<0||sx>2||sy<0||sy>3)//越界跳过 continue; if(ans[sx][sy]==-1) continue; if(fabs(ans[sx][sy]-num)==1) return false; } return true;}void dfs(int x, int y)//位置的横坐标、纵坐标{ for(int i=0;i<=9;i++) { if(!bns[i]&&check(x,y,i))//没有使用过i，并且检查可用 { bns[i]=true; ans[x][y]=i; if(x==2&&y==2) { sum++; } else { if(y!=3) dfs(x,y+1); else { dfs(x+1,0); } } bns[i]=false; ans[x][y]=-1; } }}int main(){ init(); dfs(0,1); printf("%d\n",sum);//1580 return 0;}
#include#include #include #include #include using namespace std;int ans[3][4];bool bns[10];int dir[4][2]={{-1,-1},{-1,0},{-1,1},{0,-1}};int sum=0;void init(){ memset(ans,-1,sizeof(ans)); memset(bns,false,sizeof(bns));}bool check(int x, int y, int num){ int sx,sy; for(int i=0;i<=3;i++) { sx=x+dir[i][0]; sy=y+dir[i][1]; if(sx<0||sx>2||sy<0||sy>3)//越界跳过 continue; if(ans[sx][sy]==-1) continue; if(fabs(ans[sx][sy]-num)==1) return false; } return true;}void dfs(int x, int y)//位置的横坐标、纵坐标{ for(int i=0;i<=9;i++) { if(!bns[i]&&check(x,y,i))//没有使用过i，并且检查可用 { bns[i]=true; ans[x][y]=i; if(x==2&&y==2) { sum++; } else { if(y!=3) dfs(x,y+1); else { dfs(x+1,0); } } bns[i]=false; ans[x][y]=-1;//优化之后这里就不用恢复现场也可以 } }}int main(){ init(); dfs(0,1); printf("%d\n",sum);//1580 return 0;}
转载地址：http://lpjyz.baihongyu.com/