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("\n"); 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!!!!