题意分析

给定一个大小为 $m\times n$ 的环面网格当前活细胞布局，求有多少个不同的上一代活细胞布局能通过生命游戏的规则演变得到该状态。网格面积不超过 16，可以对所有 $2^{mn}$ 种候选上一代配置暴力枚举。

解题思路

1. 对状态定义：用一个整数 $ ext{mask}$ 表示上一代布局，第 $p$ 个bit（$0\le p<mn$）为 1 表示该位置活，否则死。目标状态也编码为 $ ext{tar}$。

2. 枚举：对 $ ext{mask}=0$ 到 $2^{mn}-1$，模拟该布局如何根据生命游戏规则产生下一代：

   • 先将 $ ext{mask}$ 解码到二维数组 $ ext{g}[i][j]$。
   • 对每个格子，统计其 8 个邻居活数，边界环绕处理。
   • 根据邻居数和当前活死决定该格生死，把结果写回 $ ext{g'}[i][j]$。
   • 最后把 $ ext{g'}$ 重新编码为整数 $ ext{nextMask}$，若 $ ext{nextMask}== ext{tar}$，则计数。

最后记录计数 $ ext{ans}$，若大于 0，输出“$\dots\ ext{ans}\ \dots$ possible ancestors.”，否则“Garden of Eden.”。

本题代码

#include <iostream>
#include <cstdio>
using namespace std;

int m, n;
int tar;

int dx[8] = {-1, 1,  0, 0, -1, -1, 1, 1};
int dy[8] = { 0, 0, -1, 1, -1,  1,-1, 1};

// 模拟给定 mask 生成下一代，判断是否等于 tar
bool check(int mask) {
    int g[16];
    // 解码
    for (int p = 0; p < m * n; ++p) {
        g[p] = (mask >> p) & 1;
    }
    int g2[16];
    
    // 模拟规则
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int idx = i * n + j;
            int cnt = 0;
            // 统计环面上邻居
            for (int k = 0; k < 8; ++k) {
                int ni = (i + dx[k] + m) % m;
                int nj = (j + dy[k] + n) % n;
                cnt += g[ni * n + nj];
            }
            if (g[idx]) {
                // 存活规则
                if (cnt == 2 || cnt == 3) g2[idx] = 1;
                else g2[idx] = 0;
            } else {
                // 出生规则
                if (cnt == 3) g2[idx] = 1;
                else g2[idx] = 0;
            }
        }
    }
    // 重新编码
    int nextMask = 0;
    for (int p = 0; p < m * n; ++p) {
        if (g2[p]) nextMask |= 1 << p;
    }
    return nextMask == tar;
}

int main() {
    int cas = 0;
    while (true) {
        cin >> m >> n;
        if (m == 0 && n == 0) break;
        if (cas++) putchar('\n');

        int k;
        cin >> k;
        tar = 0;
        for (int i = 0; i < k; ++i) {
            int r, c;
            cin >> r >> c;
            tar |= 1 << (r * n + c);
        }
        int total = 1 << (m * n);
        int ans = 0;
        for (int mask = 0; mask < total; ++mask) {
            if (check(mask)) ++ans;
        }
        printf("Case %d: ", cas + 1);
        if (ans > 0) printf("%d possible ancestors.", ans);
        else printf("Garden of Eden.");
    }
    return 0;
}