方格填数
如下的10个格子
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
#include <stdio.h>
#include <math.h>
#define bool int
#define false 0
#define true 1
int flag[3][4]; //表示哪些可以填数
int mpt[3][4]; //填数
bool visit[10]; //记下被使用过的数字
int ans = 0;
void init() { //初始化
int i,j;
for(i = 0 ; i < 3 ; i ++)
for(j = 0 ; j < 4 ; j ++)
flag[i][j] = 1;
flag[0][0] = 0;
flag[2][3] = 0;
}
void Solve(){
int dir[8][2] =
{ 0, 1,//左
0, -1,//右
1, 0,//下
-1, 0,//上
1, 1,//左下
1, -1,//右下
-1, 1,//右上
-1, -1 //左上
}; //8个方向
int book = true;
for(int i = 0 ; i < 3 ; i ++){//遍历元素
for(int j = 0 ; j < 4; j ++){
//判断每个数周围是否满足
if(flag[i][j] == 0) continue;//跳过不能填的地方
for( int k = 0 ; k < 8 ; k ++){//每个方向挨个判断 依次 左->右->下->上->左下->右下->右上->左下。
int x,y;
x = i + dir[k][0];//k在变 依次取出二维数组dir的每一行的两个值 相加得 该方向的上的坐标 x y。
y = j + dir[k][1];
if(x < 0 || x >= 3 || y < 0 || y >= 4 || flag[x][y] == 0) continue;//若数组越界 或 当前值周围是特殊的地方头尾两空 则 跳过
if(abs(mpt[x][y]/*某方向的数字 */ - mpt[i][j]/* 该数字*/) == 1) book = false;//做差 若数值相邻的话就 book 置为0
}
}
}
if(book) ans ++;//计数
}
void dfs(int index){
int x,y;//下角标
x = index / 4;
y = index % 4;
if( x == 3){//出口 x == 3 表明 三行走完 赋值完毕
Solve();//判断
return;
}
if(flag[x][y]){//是否为可行的地方
for(int i = 0 ; i < 10 ; i ++){
if(!visit[i]){
visit[i] = true;//标记
mpt[x][y] = i;//赋值
dfs(index+1);//递归下一位
visit[i] = false;//取消标记
}
}
}
else
{
dfs(index+1);
}
}
int main(){
init();
dfs(0);
printf("%d\n",ans);
return 0;
}
