如下的10个格子（参看【图1.jpg】）
填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
#include <iostream>
#include <cmath>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std; const int INF = ;
const int ROW = , COL = ;
int dir[][] = {{-, }, {-, }, {, }, {, },
{, }, {, -}, {, -}, {-, -}};
int ans;
bool used[ROW][COL];
int maze[ROW][COL];
void input();
bool check( int r, int c);
bool judge(int r, int c);
void solve();
int a[] = {, , , , , , , , ,}; void input()
{
maze[][] = maze[][] = INF;
memset(used, false, sizeof(used));
} bool judge(int r, int c)
{
return (r >= && r < ) && (c >= && c < );
} //判断
bool check(int r, int c)
{
if (r == && c == ) return false;
if (r == && c == ) return false;
for (int k = ; k < ; k++) {
int nx = r + dir[k][], ny = c + dir[k][];
if (judge(nx, ny) && abs(maze[nx][ny] - maze[r][c]) == ) {
return false;
}
}
return true;
} void solve()
{
input();
do {
int i, j;
//这里就是 把全排列形成的数字, 按照 如此放在格子中
// INF 0 0 0
// 0 0 0 0
// 0 0 0 INF
for (i = ; i < COL; i++) {
maze[][i] = a[i-];
}
for (j = ; j < COL; j++) {
maze[][j] = a[COL + j - ];
}
for (j = ; j < COL - ; j++) {
maze[][j] = a[COL * + j - ];
} int flag = true;
for (i = ; i < ROW; i++) {
for (j = ; j < COL; j++) {
if (!check(i, j) && (i != || j != ) && (i != || j != )) {
flag = false;
goto num;
}
}
}
num:
if (flag) {
ans++;
}
} while (next_permutation(a, a + )); cout << ans << endl;
} int main()
{
solve();
return ;
}
//使用全排列，将不同组合的数字，分别放到10个格子中。 //然后对10个格子枚举，判断每个格子的周围是否有与之连续的数字，有则跳出整个循环，可以使用goto,会简单些 //判断完10个格子都没有相邻数字重复的，则说明，方案数++