首页 > 代码库 > hdu 1426 Sudoku Killer(DFS)

hdu 1426 Sudoku Killer(DFS)

技术分享
 1 #include <iostream> 2 #include <memory.h> 3 #include <vector> 4 #include <string> 5 #include <cstdio> 6 using namespace std; 7  8 int row[11][11],col[11][11],blo[11][11],mp[11][11]; 9 struct node{10     int x,y;11 };12 node unknow[111];13 int cnt;14 15 16 void show_result()17 {18     for (int i = 0; i < 9; ++ i) {19         for (int j = 0;j < 9; ++ j) {20             cout << mp[i][j] ;21             if (j == 8) puts("");22             else cout << " ";23         }24     }25 }26 27 int dfs(int now)28 {29     if (now == cnt) return 1;30     int xx, yy;31     xx = unknow[now].x;32     yy = unknow[now].y;33     int block = (xx/3)*3 + yy/3;34     for (int i = 1;i <= 9; ++ i) {35         if (row[xx][i] == 0 && col[yy][i] == 0 && blo[block][i] == 0) {36             mp[xx][yy] = i;37             row[xx][i] = 1;38             col[yy][i] = 1;39             blo[block][i] = 1;40             if (dfs(now + 1)) return 1;41             row[xx][i] = 0;42             col[yy][i] = 0;43             blo[block][i] = 0;44         }45     }46     return 0;47 }48 49 void init()50 {51 52     memset(row,0,sizeof(row));53     memset(col,0,sizeof(col));54     memset(blo,0,sizeof(blo));55     cnt = 0;56 }57 58 59 int main()60 {61     char temp[30];62     int ok = 1;63     while (cin >> temp) {64         if (ok) ok = 0;65         else cout << endl;66         init();67         if (temp[0] == ?)68         {69             unknow[cnt].x = 0;70             unknow[cnt++].y = 0;71         }72         else  {73             mp[0][0] = temp[0] - 0;74             row[0][mp[0][0]] = 1;75             col[0][mp[0][0]] = 1;76             blo[0][mp[0][0]] = 1;77         }78 79         for (int i = 0;i < 9; ++ i)80             for (int j = 0;j < 9; ++ j) {81                 if (i == 0 && j == 0) continue;82                 cin >> temp[0];83                 if (temp[0] == ?) {84                     unknow[cnt].x = i;85                     unknow[cnt++].y = j;86                 }87                 else  {88                     mp[i][j] = temp[0] - 0;89                     row[i][mp[i][j]] = 1;90                     col[j][mp[i][j]] = 1;91                     blo[(i/3)*3 + j/3][mp[i][j]] = 1;92                 }93             }94         dfs(0);95         show_result();96     }97     return 0;98 }
代码君

 

深搜,每次检查行,列和块。

 

int型函数不写return 是会WA的。

 

醉了。

hdu 1426 Sudoku Killer(DFS)