Problem:

题目

Solution：

状压dp，注意：
（1）当前行状态和题中状态冲突
（2）当前状态中出现两个相邻的 1
（3）上一行与当前行状态冲突（上下同时出现 1）

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;i++)
#define _rof(i,s,t) for(int i=s;i>t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define Ri(x) scanf("%d",&x)
#define Rii(x,y) scanf("%d%d",&x,&y)
#define INF 0x3f3f3f3f
using namespace std;
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
typedef long long ll;
const int maxn = 1e1 + 10;
const int mod = 100000000;
int stat[maxn],dp[maxn][1 << 13];
int main(){
    IOS;
    int n,m,v;
    while(cin>>n>>m){
        memset(stat,0,sizeof mp);
        memset(dp,0,sizeof dp);
        rep(i,1,n){
            _for(j,0,m){
                cin>>v;
                stat[i] |= (v << j);
            }
//            cout<<stat[i]<<endl;
        }
        dp[0][0] = 1;
        rep(i,1,n){// 枚举行 
            _for(j,0,(1 << m)){// 枚举当前行状态 
                if((j | stat[i]) != stat[i]){// 当前行状态和题中状态冲突 
                    continue;
                }
                if(j & (j >> 1)){// 当前状态中出现两个相邻的 1 
                    continue;
                }
                _for(k,0,(1 << m)){// 枚举上一行 
                    if(k & j){// 上一行与当前行状态冲突（上下同时出现 1） 
                        continue;
                    }
                    dp[i][j] += dp[i - 1][k];
                    dp[i][j] %= mod;
                }
            }
        }
        int ans = 0;
        _for(i,0,(1 << m)){
            ans += dp[n][i];
            ans %= mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}