dfs 填数游戏

这道题用dfs做，建一个3x4的矩阵，注意一下搜索的顺序。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std; int a[3][4] = {
   -20};// 必须要初始化！！！！
int vis[10];
int ans; int check(int x,int y,int v){
   
    int dir[4][2] = {
   {
   0,-1},{
   -1,-1},{
   -1,0},{
   -1,1}};//只需要判断之前填过的位置就可以了
    for(int i = 0; i < 4; i++){
   
        int xx = x + dir[i][0];
        int yy = y + dir[i][1]; if(xx >= 0 && xx < 3 && yy >= 0 && yy < 4){
   
            if(abs(v-a[xx][yy]) == 1) return 0;
        }
    }
    return 1;
}
void dfs(int x,int y){
   
    if(x == 2 && y == 3){
   
        ans++;
        return ;
    }
    for(int i = 0; i <= 9; i++){
   
        if(!vis[i] && check(x,y,i)){
   
            vis[i] = 1;
            a[x][y] = i;
            if(y+1 < 4)
                dfs(x,y+1);
            else
                dfs(x+1,0);
            vis[i] = 0;
        }
    }
}
int main(){
   
    memset(vis,0,sizeof(vis));
    ans = 0;
    dfs(0,1);
    cout << ans << endl;
    return 0;
}