HJ44 Sudoku

真开心，之前写过华为的数独题，直接提交就OK了=v=

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[10][10],mp[10][10][10],cnt_mp[10][10],num_sta=0,ans[10][10];
 4 bool b[10],fg[10],fd=0;
 5 struct Sta{
 6     int x,y;
 7 }sta[100];
 8 struct ID{
 9     int x,y;
10 }id[10][10];
11 void Dfs(int k){
12     if(k>num_sta){
13         fd=1;
14         for(int i=1;i<=9;i++)
15             for(int j=1;j<=9;j++)
16                 ans[i][j]=a[i][j];
17         return;
18     }
19     if(fd)return;
20     int x=sta[k].x,y=sta[k].y;
21     for(int i=1;i<=cnt_mp[x][y];i++){
22         if(fd)return;
23         int wl=mp[x][y][i];
24         for(int j=1;j<=9;j++)fg[j]=1;
25         for(int j=1;j<=9;j++)if(j!=y)fg[a[x][j]]=0;
26         if(fg[wl]==0) continue;
27         for(int j=1;j<=9;j++)fg[j]=1;
28         for(int j=1;j<=9;j++)if(j!=x)fg[a[j][y]]=0;
29         if(fg[wl]==0) continue;
30         for(int j=1;j<=9;j++)fg[j]=1;
31         for(int dx=-1;dx<=1;dx++){
32             for(int dy=-1;dy<=1;dy++){
33                 fg[a[id[x][y].x+dx][id[x][y].y+dy]]=0;
34             }
35         }
36         if(fg[wl]==0) continue;
37         a[x][y]=wl;
38         Dfs(k+1);
39         a[x][y]=0;
40     }
41     return;
42 }
43 int main(){
44     for(int i=1;i<=9;i++){
45         for(int j=1;j<=9;j++){
46             scanf("%d",&a[i][j]);
47             id[i][j].x=(((i+2)/3)-1)*3+2;
48             id[i][j].y=(((j+2)/3)-1)*3+2;
49         }
50     }
51     for(int i=1;i<=9;i++){
52         for(int j=1;j<=9;j++)
53             if(a[i][j]==0){
54                 sta[++num_sta].x=i;
55                 sta[num_sta].y=j;
56                 for(int k=1;k<=9;k++)b[k]=1;
57                 for(int k=1;k<=9;k++){
58                     if(a[i][k]) b[a[i][k]]=0;
59                     if(a[k][j]) b[a[k][j]]=0;
60                 }
61                 for(int dx=-1;dx<=1;dx++){
62                     for(int dy=-1;dy<=1;dy++){
63                         b[a[id[i][j].x+dx][id[i][j].y+dy]]=0;
64                     }
65                 }
66                 for(int k=1;k<=9;k++)
67                     if(b[k]){
68                         cnt_mp[i][j]++;
69                         mp[i][j][cnt_mp[i][j]]=k;
70                     }
71             }
72     }
73     Dfs(1);
74     for(int i=1;i<=9;i++){
75         for(int j=1;j<=9;j++)printf("%d ",ans[i][j]);
76         puts("");
77     }
78     return 0;
79 }