题目描述

农夫约翰的土地由 M×N 个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式

第 1 行包含两个整数 M 和 N。

第 2..M+1 行：每行包含 N 个整数 0 或 1，用来描述整个土地的状况，1 表示该块土地肥沃，0 表示该块土地不育。

输出格式

输出总种植方法对 108 取模后的值。

输入样例

2 3
1 1 1
0 1 0

输出样例

2 3
1 1 1
0 1 0

#include <iostream>
#include <vector>
using namespace std;
const int N = 13,M = 1<<12,mod = 2e8;
int f[N][M],cnt[M];int n,m,k;
vector<int> state,h[M];
int a[N][N],w[N];
bool check(int state)
{
    for (int i = 0; i < m; i ++ )
        if ((state >> i & 1) && (state >> i + 1 & 1))
            return false;
    return true;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];
            w[i] += !a[i][j] * (1 << j);
        }

    for(int i=0;i<1<<m;i++)
        if(check(i))
            state.push_back(i);
    int d = state.size();
//    cout<<d<<" "<<k<<endl;
//    system("pause");
    f[0][0] = 1;
    for(int i=1;i<=n+1;i++)
        for(int b=0;b<d;b++)//i行状态
        {
            if(state[b]&w[i]) continue;
            for(int k=0;k<d;k++)//i-1行状态
            {
                if(state[k]&w[i-1]) continue;
                if(!(state[k]&state[b])) 
                    f[i][b]=(f[i][b]+f[i-1][k])%mod;
            }
        }
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=0;j<state.size();j++)
    //         cout<<f[i][j]<<" ";
    //     puts("");
    // }

    cout<<f[n+1][0];
    return 0;
}