2016年 蓝桥杯 方格填数

问题引入

方格填数

如下的10个格子
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+

（如果显示有问题，也可以参看【图1.jpg】）

填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

#include<stdio.h>
#include<math.h>
int ans=0;
int book[10];
int a[5][6];

int check(int i,int j)    //判断i,j是否可填k 
{
    int x,y;
    for(x=i-1;x<=i+1;x++)
    {
        for(y=j-1;y<=j+1;y++)
        {
            if(abs(a[x][y] - a[i][j])==1)
                return 0;
        }
    }
    return 1;    
}
void init()        //构建5x6的方格，初始数值为-10 
{
    int i,j;
    for(i=0;i<5;i++)
    {
        for(j=0;j<6;j++)
        {
            a[i][j] = -10;
        }
    }
 } 

void f(int x,int y)
{
    int k;
    if(x == 3 && y == 4)
    {
        ans++;
        return;
    }
    
    for(k=0;k<10;k++)
    {
        if(book[k] == 0)
        {
            a[x][y] = k;
            
            if(!check(x,y))    //提前检知，回复并continue 
            {
                a[x][y]=-10;
                continue;
            }
            
            book[k] = 1;
            
            if(y==4){
                f(x+1,1);}
            else{
                f(x,y+1);}
            
            {
            book[k] = 0;
            a[x][y] = -10;
            }
        }
    }
    
 } 
 
int main()
{
    init();
    f(1,2);
    printf("%d",ans);
    return 0;
 }