方格填数

方格填数 如下的10个格子 填入0~9的数字。要求：连续的两个数字不能相邻。 （左右、上下、对角都算相邻） 一共有多少种可能的填数方案？ 请填写表示方案数目的整数。 注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。 注意：在最开始我将设置空格转换为一维数组，我看似觉得思路很正确但是却忽略了对于边界的检验  bool check(int *a,int i)//合理性检查 { if (abs(a[i] - a[i - 1]) <=1)return false;//左边 if (abs(a[i] - a[i - 4]) <= 1) return false;//上边 if (abs(a[i] - a[i - 3]) <= 1) return false;//左上 return true; } 此种算法看似正确但是却忽略了最致命的错误我，由于是一维数组所以我将填充下标从1-10的空格，在下标为4的空格，即第二行第一列的，此时他没有左边，他的左边在代码中显示为空，很显然这是最致命的错误 这是正确的采用一维数组的解析过程，比较暴力 #include<iostream> using namespace std; int a[11], vis[11]; int count1; /*采用先将所有的位置设置好，然后将其进行筛选*/ void DFS(int x) { if (x>10)//所有方格填数完毕    { if (abs(a[1] - a[2])>1 && abs(a[1] - a[4])>1 && abs(a[1] - a[5])>1 && abs(a[1] - a[6])>1 && abs(a[2] - a[3])>1 && abs(a[2] - a[5])>1 && abs(a[2] - a[6])>1 && abs(a[2] - a[7])>1 && abs(a[3] - a[6])>1 && abs(a[3] - a[7])>1 && abs(a[4] - a[5])>1 && abs(a[4] - a[8])>1 && abs(a[4] - a[9])>1 && abs(a[5] - a[6])>1 && abs(a[5] - a[8])>1 && abs(a[5] - a[9])>1 && abs(a[5] - a[10])>1 && abs(a[6] - a[7])>1 && abs(a[6] - a[9])>1 && abs(a[6] - a[10])>1 && abs(a[7] - a[10])>1 && abs(a[8] - a[9])>1 && abs(a[9] - a[10])>1) { /*打印输出每种情况*/ for (int i = 1; i < 11; i++) cout << a[i] << " "; cout << endl; count1++; } } for (int i = 0; i <= 9; i++) if (vis[i] == 0) { vis[i] = 1;//将用过的数标记    a[x] = i;//填数    DFS(x + 1);//对下一个方格继续填数    vis[i] = 0;//清除标记    } } int main() { count1 = 0; DFS(1); cout << count1 << endl; return 0; } 我的想法是采用动态规划，一步一步进行求解，从第一个填空处开始，每赋值一次进行一次合法性判断，如果不满足，切换另一个数值，如果符合则进行递归