分析

f[i][j]表示前i行已种完，目前在第i行，状态为j的摆放方案集合
状态转移方程：$$ f[i][j]=(f[i][j]+f[i-1][k])\bmod10^{8} $$

k能转移到j的条件：
1. (j&k)==0,j,k两行不重复

j,k为合法方案条件：同一行中没有相邻的两个1。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 14,M=(1<<12),mod=100000000;
int n,m,g[N],state[M],idx;  //g用来存储地图，state用来存储合法方案
vector<int> head[M];    //计算合法方案可以转移的到的方案
long long f[N][M];
bool check(int x)   //判断是否有相邻的1
{
    for(int i=0;i<m-1;i++)
        if((x>>i & 1) && (x>>(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;
            g[i]+= (!t)<< j;    //写成g[i]+= (!t)<< (m-j-1); 更符合题意，但都不影响解题。
        }
    }

    for(int i=0;i<(1<<m);i++)   //记录所有合法状态
        if(check(i)) state[idx++]=i;
    for(int i=0;i<idx;i++)
    {
        for(int j=0;j<idx;j++)
        {
            int a=state[i],b=state[j];
            if((a&b)==0)    //状态可以进行转移，加入到状态转移数组中
                head[i].push_back(j);
        }
    }

    f[0][0]=1;
    for(int i=1;i<=n+1;i++)
    {
        for(int j=0;j<idx;j++)
        {
            for(auto k:head[j])
            {
                if(g[i] & state[j]) continue;   //当前状态与本图实际状态冲突，continue
                f[i][j]=(f[i][j]+f[i-1][k])%mod;
            }
        }
    }
    cout<<f[n+1][0];    //表示前n+1行已经摆好，在第n+1行，状态为0(本行没有种玉米)的方案数
    return 0;
}