题意分析

这一题无非是在小国王的基础上加上了荒废的土地，又因为荒废的土地也是不能进行种植的，所以可以把这一个位置转换为二进制状态下的1，也就是不能进行使用的状态，这样本题就和小国王这一题差不多了。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N =14,M=1<<12,mod=1e8;
int n,m;
int w[N];
vector<int> state;
vector<int> head[M];
int f[N][M];

bool check(int state)
{
    for(int i=0;i+1<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++)//列
        {
            int t;
            cin>>t;
           w[i]+=!t*(1<<j);  //将荒废的土地转为二进制状态下的1.
           //0和1在最下面有解释
        }

    for(int i=0;i<1<<m;i++)   //预处理，找出合法状态  //在行的方向上找到了合法
      if(check(i))
        state.push_back(i);

        //合法方案的状态转移，简单的说就是第i行和第i-1行的状态，
        //是否可以进行转移。
    for(int i=0;i<state.size();i++)
       for(int j=0;j<state.size();j++)     //在列的方向上可以相互转移
         {
             int a=state[i],b=state[j];
             if(!(a&b))
               head[i].push_back(j);
         }

    f[0][0]=1;
    for(int i=1;i<=n+1;i++)
       for(int j=0;j<state.size();j++)
          if(!(state[j]&w[i]))             //在第i行，状态a是否满足在荒废土地没有种植玉米
            for(int k:head[j])
              f[i][j]=(f[i][j]+f[i-1][k])%mod;

    cout<<f[n+1][0]<<endl;//可仿照小国王这一题的状态表示。都为在前i行摆放完毕的情况下，第i行所处的状态。
    //0为这一行已经摆放完毕，1表示未摆放完毕。
    return 0;
}