UVA 211 - The Domino Effect（dfs+剪枝）(二)
sizeof(vis)); for (int i = 0; i < 7; i++) for (int j = 0; j < 8; j++) { if (i == 0 && j == 0) continue; scanf("%d", &g[i][j]); } } bool judge(int x) { for (int j = 0; j < 8; j++) if (vis[x][j] == 0) return true; return false; } void dfs(int x, int y, int nu) { if (nu == 28) { ans++; for (int i = 0; i < 7; i++) { for (int j = 0; j < 8; j++) printf("%4d", res[i][j]); printf("\n"); } printf("\n"); return; } if (x == 7) return; if (y == 8) { if (judge(x)) return; dfs(x + 1, 0, nu); return; } if (vis[x][y]) { dfs(x, y + 1, nu); return; } for (int i = 0; i < 2; i++) { if (i == 0 && x == 6) continue; if (i == 1 && y == 7) continue; int xx = x + d[i][0]; int yy = y + d[i][1]; if (vis[xx][yy]) continue; if (v[num[g[x][y]][g[xx][yy]]]) continue; res[x][y] = res[xx][yy] = num[g[x][y]][g[xx][yy]]; vis[x][y] = vis[xx][yy] = v[num[g[x][y]][g[xx][yy]]] = 1; dfs(x, y + 1, nu + 1); vis[x][y] = vis[xx][yy] = v[num[g[x][y]][g[xx][yy]]] = 0; } } void solve() { if (cas) printf("\n\n\n"); printf("Layout #%d:\n\n", ++cas); for (int i = 0; i < 7; i++) { for (int j = 0; j < 8; j++) printf("%4d", g[i][j]); printf("\n"); } printf("\nMaps resulting from layout #%d are:\n\n", cas); dfs(0, 0, 0); printf("There are %d solution(s) for layout #%d.\n", ans, cas); } void table() { int cnt = 1; for (int i = 0; i <= 6; i++) for (int j = i; j <= 6; j++) { num[i][j] = num[j][i] = cnt++; } } int main() { table(); while (~scanf("%d", &g[0][0])) { init(); solve(); } return 0; }