如下的10个格子
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+
（如果显示有问题，也可以参看【图1.jpg】）
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
拿到这道题我就知道搜一搜就好了，但是怎么搜索呢？一共十个格子，可以填10个数字，直接暴力那么就是10^10的运算量。。。这可以跑好一段时间了。但是我们可以发现，有很多情况没有到最后一个点整个图就已经无法成立了，所以用dfs剪枝一下就很好出来了。我这里给出的是数字不能重复的1580的做法。
首先，把整个图扩大一环，把整个图填入INF，然后从G【1】【2】这个点开始dfs下去计数即可。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int cnt, G[5][6], vst[15];
bool Check(int x, int y)
{
for(int i = -1; i < 2; i++)
for(int j = -1; j < 2; j++)
if(abs(G[x + i][y + j] - G[x][y]) == 1)
return false;
return true;
}
void dfs(int x, int y)
{
if(x == 3 && y == 4)
{
cnt++;
return;
}
int nx, ny;
for(int i = 0; i <= 9; i++)
{
if(!vst[i])
{
vst[i] = 1;
G[x][y] = i;
if(Check(x, y))
{
nx = (y == 4 ? x + 1 : x);
ny = (y == 4 ? 1 : y + 1);
dfs(nx, ny);
}
vst[i] = 0;
}
}
G[x][y] = INF;
}
int main()
{
for(int i = 0; i < 5; i++)
for(int j = 0; j < 6; j++)
G[i][j] = INF;
for(int i = 0; i <= 9; i++)
{
vst[i] = 1;
G[1][2] = i;
dfs(1, 3);
vst[i] = 0;
}
cout << cnt << endl;
return 0;
//1580
}