【dfs】数独

Luogu P1784 数独

dfsQAQ
枚举每个格子填什么，符合要求的就填不符合的就不填qwq
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 using namespace std;
 5 const int sz = 10;
 6 int plat[sz][sz];
 7 bool h[sz][sz],l[sz][sz],small[sz][sz];
 8 void print() {
 9     for(int i = 1; i <= 9; i++) {
10         for(int j = 1; j <= 9; j++) {
11             printf("%d ",plat[i][j]);
12         }
13         printf("
");
14     }
15     exit(0);
16 }
17 void dfs(int x, int y) {
18     if(plat[x][y]) {
19         if(x == 9 && y == 9) print();
20         if(y == 9) dfs(x + 1, 1); 
21         else dfs(x, y + 1);
22     }
23     if(!plat[x][y]) {
24         for(int i = 1; i <= 9; i++) { 
25             if(!h[x][i] && !l[y][i] && !small[(x-1)/3*3+(y-1)/3+1][i]) {
26                 plat[x][y] = i, h[x][i] = 1, l[y][i] = 1, small[(x - 1) / 3 * 3 + (y - 1) / 3 + 1][i] = 1;
27                 if(x == 9 && y == 9) print();
28                 if(y == 9) dfs(x + 1, 1); 
29                 else dfs(x, y + 1);
30                 plat[x][y] = 0, h[x][i] = 0, l[y][i] = 0, small[(x - 1) / 3 * 3 +(y - 1) / 3 + 1][i] = 0;
31             }
32         } 
33     }
34 }
35 int main()
36 {
37     for(int i = 1; i <= 9; i++) {
38         for(int j = 1; j <= 9; j++) {
39             scanf("%d", &plat[i][j]);
40             if(plat[i][j]) {
41                 h[i][plat[i][j]] = 1;
42                 l[j][plat[i][j]] = 1;
43                 small[(i - 1) / 3 * 3 + (j - 1) / 3 + 1][plat[i][j]] = 1;
44             }
45         }
46     } 
47     dfs(1,1);
48     return 0;
49 }
//以后玩数独有外挂啦qwq！！！！