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

For(j, 1 << m)
    if ((j & line[i]) == j && (j & (j >> 1)) == 0) // 先检测本行是否有相邻的
        For(k, 1 << m)
            if ((j & k) == 0) // 再枚举上一行,检测是否与本行有相邻的
                dp[now][j] += dp[pre][k];
/*0ms,216KB*/

const int mx = 12;
const int mod = 100000000;

int dp[2][1 << mx], line[mx]; ///把输入压缩下。

int f(int n, int m)
{
    int i, j, k, pre, now;
    mem(dp[0], 0);
    dp[0][0] = 1;
    For(i, n)
    {
        pre = i & 1, now = pre ^ 1;
        mem(dp[now], 0);
        For(j, 1 << m)
            if ((j & line[i]) == j && (j & (j >> 1)) == 0)
                For(k, 1 << m)
                    if ((j & k) == 0)
                        dp[now][j] += dp[pre][k];
    }
    return Acc(dp[now], 1 << m) % mod; ///由于未取模的结果不超int,所以最后取下模就行
}

int main()
{
    int n, m, i, j, x;
    while (~SII(n, m))
    {
        mem(line, 0);
        For(i, n) For(j, m) SI(x), line[i] |= x << j;
        PI(f(n, m));
    }
    return 0;
}

Comments

comments powered by Disqus