首页 > 代码库 > UVa211 The Domino Effect (DFS)
UVa211 The Domino Effect (DFS)
链接:http://vjudge.net/problem/35575
分析:dfs暴力。
1 #include <cstdio> 2 #include <cstring> 3 4 const int r = 7; 5 const int c = 8; 6 const int m = 30; 7 const int dir[2][2] = { 8 {0, 1}, 9 {1, 0},10 };11 12 int map[r][c], id[r][r], checked[m], vis[r][c], ans;13 14 void build() {15 int num = 1;16 for (int i = 0; i < r; i++)17 for (int j = i; j < r; j++)18 id[i][j] = id[j][i] = num++;19 }20 21 bool init() {22 ans = 0;23 memset(checked, 0, sizeof(checked));24 memset(vis, 0, sizeof(vis));25 for (int i = 0; i < r; i++)26 for (int j = 0; j < c; j++)27 if (scanf("%d", &map[i][j]) != 1) return false;28 return true;29 }30 31 void print() {32 for (int i = 0; i < r; i++) {33 for (int j = 0; j < c; j++) printf("%4d", vis[i][j]);34 printf("\n");35 }36 printf("\n");37 }38 39 void dfs(int x, int y, int cnt) {40 if (cnt == 28) {41 ans++;42 print();43 return;44 }45 if (y == c) { x++; y = 0; }46 47 if (vis[x][y]) dfs(x, y + 1, cnt);48 else {49 for (int i = 0; i < 2; i++) {50 int nx = x + dir[i][0], ny = y + dir[i][1];51 if (nx >= r || ny >= c || vis[nx][ny]) continue;52 int n = id[map[x][y]][map[nx][ny]];53 if (checked[n]) continue;54 vis[x][y] = vis[nx][ny] = n; checked[n] = 1;55 dfs(x, y + 1, cnt + 1);56 vis[x][y] = vis[nx][ny] = 0; checked[n] = 0;57 }58 }59 }60 61 int main() {62 build();63 int kase = 0;64 while (init()) {65 if (kase) printf("\n\n\n");66 printf("Layout #%d:\n\n", ++kase);67 for (int i = 0; i < r; i++) {68 for (int j = 0; j < c; j++)69 printf("%4d", map[i][j]);70 printf("\n");71 }72 printf("\nMaps resulting from layout #%d are:\n\n", kase);73 dfs(0, 0, 0);74 printf("There are %d solution(s) for layout #%d.\n", ans, kase);75 }76 return 0;77 }
UVa211 The Domino Effect (DFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。