方格填数
如下的10个格子
（如果显示有问题，也可以参看【图1.jpg】）
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路就是用深搜先找到所有0-9的全排列，没找到一个就把这10个数的顺序复制给上图的空格中，
然后判断一下是否相邻之间的两个数相差1即可。
哎，刚开始solve()中因为有BUG，所以我打印了一下保存全排列数组的元素，运行了半个小时才差不多把01....、02......、03........输出完。
一想全排列的总个数是n的阶乘个啊，3628k+。我就开始怀疑这道题的深搜算法是否高效的问题了。
毁了啊，其实不应该打印数组中的元素的，用半个小时的时间全放在输出上了。233333....
其实效率倒还可以的。
运行结果：
1580 Process returned 0 (0x0) execution time : 2.978 s Press any key to continue.
#include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cmath> #include <algorithm> #include <cstring> #include <map> #include <sstream> #include <queue> #include <stack> #define INF 0x3f3f3f3f #define mem(a,b) memset(a,b,sizeof(a)) #define For(a,b) for(int i = a;i<b;i++) #define ll long long #define MAX_N 100010 using namespace std; int mpt[10][10]; int f[10][10]; bool vis[20]; int pp[20]; int ans; void solve() { int r = 0; for(int i = 0; i<3; i++) { for(int j = 0; j<4; j++) { if(f[i][j]) { mpt[i][j] = pp[r ++]; } } } // for(int i = 0; i<3; i++) // for(int j = 0; j<4; j++) // cout<<mpt[i][j]<<' '; // cout<<endl; int cur[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1}; bool flag = true; for(int i = 0; i<3; i++) { for(int j = 0; j<4; j++) { if(!(i==0&&j==0) && !(i==2&&j==3)) { for(int k = 0; k<8; k++) { int dx = i + cur[k][0]; int dy = j + cur[k][1]; if(dx>=0 && dx<=2 && dy>=0 && dy<=3 && f[dx][dy] != 0) { if(abs(mpt[i][j] - mpt[dx][dy]) == 1) { flag = false; } } } } } } if(flag) ans ++; return ; } void dfs(int x) { if(x == 10) { solve(); return ; } for(int i = 0; i<10; i++) { if(!vis[i]) { vis[i] = true; pp[x] = i; dfs(x+1); vis[i] = false; } } } int main() { for(int i = 0; i<3; i++) for(int j = 0; j<4; j++) f[i][j] = 1; f[0][0] = 0; f[2][3] = 0; mem(mpt,0); mem(pp,0); mem(vis,false); ans = 0; dfs(0); printf("%d\n",ans); return 0; }
