原博

方格填数

如下的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;
}