POJ 2733 - The Game of Efil

http://poj.org/problem?id=2733

概要

いわゆるライフゲームを考える。 一世代後に与えられた \(m \times n\) の状態になるような状態はいくつあるか答える。

制約

解法

全探索。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 bool test(int g[20][20], int h[20][20], int H, int W)
 6 {
 7   for (int i = 0; i < H; i++) {
 8     for (int j = 0; j < W; j++) {
 9       int c = 0;
10       for (int d = 0; d < 8; d++) {
11         static const int di[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dj[] = {-1, 0, 1, -1, 1, -1, 0, 1};
12         const int k = (i + di[d] + H) % H;
13         const int l = (j + dj[d] + W) % W;
14         c += g[k][l];
15       }
16       if (g[i][j]) {
17         if (h[i][j] != (c == 2 || c == 3)) {
18           return false;
19         }
20       } else {
21         if (h[i][j] != (c == 3)) {
22           return false;
23         }
24       }
25     }
26   }
27   return true;
28 }
29 
30 int main()
31 {
32   int H, W;
33   for (int Ti = 1; scanf("%d %d", &H, &W) != EOF && H != 0; Ti++) {
34     int grid[20][20];
35     for (int i = 0; i < H; i++) {
36       fill_n(grid[i], W, false);
37     }
38     int K;
39     scanf("%d", &K);
40     for (int i = 0; i < K; i++) {
41       int r, c;
42       scanf("%d %d", &r, &c);
43       grid[r][c] = true;
44     }
45     const int N = H*W;
46 
47     int g[20][20];
48     int ans = 0;
49     for (unsigned s = 0; s < (1U<<N); s++) {
50       for (int i = 0; i < N; i++) {
51         g[i/W][i%W] = !!(s & (1U<<i));
52       }
53       if (test(g, grid, H, W)) {
54         ++ans;
55       }
56     }
57     printf("Case %d: ", Ti);
58     if (ans == 0) {
59       puts("Garden of Eden.");
60     } else {
61       printf("%d possible ancestors.\n", ans);
62     }
63   }
64   return 0;
65 }
poj/2733.cc