首页 > 代码库 > 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)