首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。