sicily 1171 The Game of Efil

sicily ACM

1. 题目大意

一块m * n的板上，格子上有一些细菌，一个细菌的八个方向上邻居细菌数如果是2或3个，那么下一代它能保留下来，否则会死掉（因为“孤独”或“拥挤”)，如果一个空格的邻居细菌数是3个，那么下一代这个格子会产生一个新的细菌。给出一个板的当前的状态，求上一代有多少种不同的情况。注意：板的上下边是连通的，左右边也是连通的。

2. 题目数据范围

m * n <= 16

3. 解题思路

枚举所有状态，根据题目要求生成下一代的状态，并与输入的状态比较，如果相等，则是其中一种可能的情况，结果加1。因为最多有16个格子，每个格子有两种状态（有细菌或无细菌），因此总的状态数是2^16。枚举状态使用深度搜索

4. 代码

// 1171.cpp
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
int m, n;
int ans;
int in[20][20];
int d[20][20];
int direction[8][2] = {{-1, -1}, {-1, 0}, {-1, 1},
                       {0, -1}, {0, 1},
                       {1, -1}, {1, 0}, {1, 1}};
void cal()
{
    int t;
    for (int i = 0; i < m; i ++)
    {
        for (int j = 0; j < n; j++)
        {
            int temp = 0;
            for (int k = 0; k < 8; k++)
            {
                //计算这个格子八个方向的格式有多少个邻居细菌，
                //因为上下是连通的，左右也是连通的，所以需要加上m(或n),然后再mod m(或n)
                if (d[(i + direction[k][0] + m) % m][(j + direction[k][1] + n) % n])
                    temp ++;
            }
            if (temp == 3)
                t = 1;
            else if (d[i][j] == 1 && temp == 2)
                t = 1;
            else
                t = 0;
            if (in[i][j] != t)
                return;
        }
    }
    ans ++;
    return;
}
// 依次从上到下，从左到右递归
void dfs(int x, int y)
{
    if (x == m) // 全部格子已遍历完
    {
        cal();
        return;
    }
    d[x][y] = 0;
    if (y == n - 1) // 到了一行的最后格子，转为下一行第一个格子
        dfs(x + 1, 0);
    else
        dfs(x, y + 1);
    d[x][y] = 1;
    if (y == n - 1)
        dfs(x + 1, 0);
    else
        dfs(x, y + 1);
}
int main()
{
    int cases = 1;
    while (scanf ("%d%d", &m, &n) && m != 0 && n != 0)
    {
        int k;
        ans = 0;
        scanf ("%d", &k);
        int x, y;
        memset(in, 0, sizeof(in)); 
        for (int i = 0; i < k; i++)
        {
            scanf ("%d%d", &x, &y);
            in[x][y] = 1;
        }
        dfs(0, 0);
        printf("Case %d: ", cases);
        if (ans)
            printf("%d possible ancestors.\n", ans);
        else
            printf("Garden of Eden.\n");
        cases ++; // 忘记加1，这里也WA了一次，如此低级的错误
    }
}