数独问题。给定其中的几个数,找出其他符合规则的数。保证所给数据合法。典型的DFS。 又是1A真爽。
首先用三个数组标记每列每行每个九宫格出现过的数字。然后DFS寻找可能的状态。跑了400+ms。
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 7 using namespace std; 8 9 int sudoku[10][10]; 10 11 bool MarkDfs,hr[10][10],hc[10][10],hs[10][10]; 12 13 int JudgeS(int i,int j) 14 { 15 if(1 <= i && i <= 3 && 1 <= j && j <= 3) 16 return 1; 17 if(1 <= i && i <= 3 && 4 <= j && j <= 6) 18 return 2; 19 if(1 <= i && i <= 3 && 7 <= j && j <= 9) 20 return 3; 21 if(4 <= i && i <= 6 && 1 <= j && j <= 3) 22 return 4; 23 if(4 <= i && i <= 6 && 4 <= j && j <= 6) 24 return 5; 25 if(4 <= i && i <= 6 && 7 <= j && j <= 9) 26 return 6; 27 if(7 <= i && i <= 9 && 1 <= j && j <= 3) 28 return 7; 29 if(7 <= i && i <= 9 && 4 <= j && j <= 6) 30 return 8; 31 if(7 <= i && i <= 9 && 7 <= j && j <= 9) 32 return 9; 33 } 34 35 void dfs(int r,int c) 36 { 37 if(MarkDfs == false) 38 return; 39 int i,j,k; 40 for(i = r;i <= 9; ++i) 41 { 42 for(j = (i == r ? c : 1);j <= 9; ++j) 43 { 44 if(sudoku[i][j] == 0) 45 { 46 for(k = 1;k <= 9; ++k) 47 { 48 if(hr[i][k] == false && hc[j][k] == false && hs[JudgeS(i,j)][k] == false) 49 { 50 hr[i][k] = true; 51 hc[j][k] = true; 52 hs[JudgeS(i,j)][k] = true; 53 sudoku[i][j] = k; 54 dfs(i,j); 55 if(MarkDfs) 56 { 57 sudoku[i][j] = 0; 58 hr[i][k] = false; 59 hc[j][k] = false; 60 hs[JudgeS(i,j)][k] = false; 61 } 62 } 63 } 64 return ; 65 } 66 } 67 } 68 MarkDfs = false; 69 } 70 71 int main() 72 { 73 int T; 74 int i,j; 75 76 scanf("%d",&T); 77 78 while(T--) 79 { 80 memset(hr,false,sizeof(hr)); 81 memset(hc,false,sizeof(hc)); 82 memset(hs,false,sizeof(hs)); 83 84 MarkDfs = true; 85 86 for(i = 1;i <= 9; ++i) 87 { 88 for(j = 1;j <= 9; ++j) 89 scanf("%1d",&sudoku[i][j]); 90 } 91 92 for(i = 1; i <= 9; ++i) 93 { 94 for(j = 1;j <= 9; ++j) 95 { 96 hr[i][sudoku[i][j]] = true; 97 hc[j][sudoku[i][j]] = true; 98 hs[JudgeS(i,j)][sudoku[i][j]] = true; 99 } 100 } 101 102 dfs(1,1); 103 104 for(i = 1;i <= 9; ++i) 105 { 106 for(j = 1;j <= 9; ++j) 107 { 108 printf("%d",sudoku[i][j]); 109 } 110 printf(" "); 111 } 112 113 } 114 return 0; 115 }