题目描述

如下的10个格子，填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）一共有多少种可能的填数方案？

image

输出

请填写表示方案数目的整数。

代码

又是一道dfs题，因为是填空题如果实在想不出可用暴搜

#include<bits/stdc++.h>
using namespace std;

int a[4][5],visit[10];
int dx[4]={-1,-1,-1,0};
int dy[4]={0,1,-1,-1};
int sum;

bool check(int x,int y,int n){
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<3&&xx>=0&&yy>=0&&yy<4){
            if(abs(a[xx][yy]-n)==1)
                return false;
        }
    }
    return true;
}

void dfs(int x,int y){
    if(x==2&&y==3){
        sum++;
        return;
    }
    for(int i=0;i<10;i++){
        if(visit[i]==0&&check(x,y,i)){
            visit[i]=1;
            a[x][y]=i;
            if(y+1<4)
                dfs(x,y+1);
            else
                dfs(x+1,0);//另起一行
            visit[i]=0;
        }
    }
}

int main(){
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            a[i][j]=-20;
    dfs(0,1);
    cout<<sum;
    return 0;
}