poj 3254 Corn Fields--状压dp入门

原题链接：​​http://poj.org/problem?id=3254​​

题意：给出一个n行m列的草地，1表示肥沃，0表示贫瘠，现在要把一些牛放在肥沃的草地上，但是要求所有牛不能相邻，问你有多少种放法。

分析：​​http://www.tuicool.com/articles/JVzMVj​​

#define _CRT_SECURE_NO_DEPRECATE
#pragma comment(linker, "/STACK:16777216")
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;
 
int n, m;
int e;
const int MOD = 100000000;
int status[13];//每行的01状态
int t[1 << 13];
int dp[13][1 << 13];

bool judge1(int x)
{
  return x&(x << 1);
}

bool judge2(int x, int y)
{
  return status[x] & t[y];
}

int main()
{
  while (~scanf("%d%d", &n, &m))
  {
    e = 0;
    memset(status, 0, sizeof(status));
    memset(dp, 0, sizeof(dp));

    int x;
    for (int i = 1; i <= n; i++)
    {
      for (int j = 1; j <= m; j++)
      {
        scanf("%d", &x);
        if (x == 0)
          status[i] += (1 << (j - 1));
      }
    }

    //保存所有相邻不是1的
    for (int i = 0; i < (1 << m); i++)
    {
      if (!judge1(i))
        t[e++] = i;
    }

    //dp初值
    for (int i = 0; i < e; i++)
    {
      if (!judge2(1, i))
        dp[1][i] = 1;
    }

    for (int i = 2; i <= n; i++)
    {
      for (int j = 0; j < e; j++)
      {
        if (judge2(i, j))//与第i行的状态比较，判断水平方向是否相邻
          continue;
        for (int k = 0; k < e; k++)//如果可以用，还要和上一行的状态比较，判断竖直方向是否相邻
        {
          if (dp[i - 1][k] && (t[j] & t[k]) == 0)//注意 & 运算符优先级
            dp[i][j] += dp[i - 1][k];
        }
      }
    }

    //最后结果
    int ans = 0;
    for (int i = 0; i < e; i++)
      ans += dp[n][i];
    printf("%d\n", ans%MOD);
  }
  return 0;
}