填写数独 洛谷P1784

题目链接：https://www.luogu.org/problemnew/show/P1784

因为要求行列以及每9个数字组成的中格子都得有1-9这9个数，我们不妨建三个二维数组

第一维代表是第几个行/列/中格子，第二维是具体数字，然后数组为1就代表第二维的数字已经有了，为0就是没有

dfs按照从左到右，从上到下的顺序来遍历

另外，存中格子的的时候1-9也是按照这个顺序来的，用（i-1）/3*3+(j-1)/3+1来表示这是第几个中格子

#include <bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
const int mod=1e9+7;
const int maxn=1e5+7;
typedef long long ll;
int a[10][10];
bool h[10][10],l[10][10],g[10][10];//三个数组分别代表行列和组，第一维是行列组的下标，第二维是1-9的莫个数，为0说明还不存在，1存在 
void print(){
    for(int i=1;i<10;i++){
        for(int j=1;j<9;j++)
        printf("%d ",a[i][j]);
        printf("%d
",a[i][9]);
    }
    exit(0);
}
void dfs(int x,int y){
    if(a[x][y]){
        if(x==9&&y==9)print();
        if(y==9) dfs(x+1,1);//从左到右，从上到下，依次遍历 
        else dfs(x,y+1);
    }
    else{
        for(int i=1;i<=9;i++){
            if(!h[x][i]&&!l[y][i]&&!g[(x-1)/3*3+(y-1)/3+1][i]){
                h[x][i]=1;l[y][i]=1;g[(x-1)/3*3+(y-1)/3+1][i]=1;
                a[x][y]=i;
                if(x==9&&y==9)print();
                if(y==9) dfs(x+1,1);
                else dfs(x,y+1);
                h[x][i]=0;l[y][i]=0;g[(x-1)/3*3+(y-1)/3+1][i]=0;
                a[x][y]=0;
            }
        }
    }    
}
int main(){
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            scanf("%d",&a[i][j]);
            if(a[i][j]>0){
                h[i][a[i][j]]=1;
                l[j][a[i][j]]=1;
                g[(i-1)/3*3+(j-1)/3+1][a[i][j]]=1;
            }    //cout<<233<<endl;
        }
    }
    dfs(1,1); 
    return 0;
}