思路

因为题目的数据很小，所以直接二进制枚举就好了。

思路就是枚举每一行的二进制形式，1表示有人，0表示没人，dp[i][[j]表示第i行的放置状态是j

下面考虑下判断操作是否合法：

1、首先上一层 放了人的地方下一层必须不放，既上一层第 i位位1，下一层第i位必须为0，上一层第 i 位为0下一层可放可不放 ， 这个操作可以用 & 运算符 j & k ，j表示上一层的状态，k表示这一层 ，当j & k 为 0 时说明这一层放置方法为k合理

2、本层Map[i] 的第j位为0表示这层不能放人，假设放置方法为 k ，则 (Map[i] & k) == k 表示操作合法（Map[i]的第j位为0如果k的第j位为0 用 & 后结果不等于 k

3、本层不能有连续的1存在，，所以用 j & （j >> 1）若不为0表示存在连续的 1

代码

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 100000000;
const int maxn = 100005;
#define stop system("pause")
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int Map[15];
int dp[15][1 << 15];
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        memset(dp,0,sizeof(dp));
        memset(Map,0,sizeof(Map));
        for(int i = 1 ; i <= n ; ++i){
            for(int j = 0 ; j < m ;++j){
                int x = read();
                Map[i] = (Map[i] << 1) + x;
            }
        }
        dp[0][0] = 1;
        for(int i = 1 ; i <= n ; ++i){//第i行
            for(int j = 0 ; j < (1 << m); ++j){//第i行的状态
                if((j & (j >> 1)) || (Map[i] & j)!= j) continue;
                for(int k = 0 ; k < (1 << m) ; ++k){//枚举上一行
                    if(j & k) continue;//j有0的k都行，j有1的k必须为0
                    dp[i][j] = (dp[i][j] + dp[i-1][k])%mod;
                }
            }
        }
        ll ans = 0;
        for(int i = 0 ; i < (1 << m) ; ++i){
            ans = (ans + dp[n][i]) % mod;
        }
        printf("%lld\n",ans);
    }
}