原题传送门
#include<bits/stdc++.h>
using namespace std;
const int N = 14, M = 1 << 12, mod = 1e8;
int n, m;
int g[N];//记录每一行的坑
vector<int> state;
vector<int> head[M];
int f[N][M];//表示第N行放置情况为M的方案数
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 ++ ){//从第一行开始,因为以后运算是要按行数,所以行的下标从1开始
for(int j = 0; j < m; j ++ ){
int t;
cin>>t;
g[i] += (!t << j);
/*
如果这个位置为0,则代表不能种玉米,就将他取反置为1,便于以后相与运算(1代表不能种的地方)
以二进制形式左移j位刚好让g[i]以二进制形式储存下第i行的排列情况
*/
}
}
for(int i = 0; i < 1 << m; i ++ ){//遍历排查每一列是否是合法情况
if(check(i)){
state.push_back(i);
}
}
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)){//相与为0即代表这两列没有重合的1的位置
head[i].push_back(j);//记录i状态可以由j状态转移而来
}
}
}
f[0][0] = 1;//第0行状态为0的方案数有1个
for(int i = 1; i <= n + 1; i ++ ){
for(int a = 0; a < state.size(); a ++ ){
for(int b : head[a]){
if(g[i] & state[a]) continue;
/*如果g[i]和state[a]相与为1,代表这两种排布状态有1重合的情况
代表这种情况种植的玉米和部分地皮无法种植冲突
这种情况应该被舍弃,因此直接跳过
*/
f[i][a] = (f[i][a] + f[i - 1][b]) % mod;//a状态由b状态转移而来
}
}
}
cout<<f[n + 1][0]<<endl;
return 0;
}