solution
状压dp。
用数字来表示一行方案,对于一个状态x,如果x的第i位(二进制下)为1,表示这一行的第i个位置安排士兵。否则表示不安排士兵。
先把每一行可能的状态都搜出来,也就是在满足相邻两个二进制位不都为1的条件下,搜出所有的方案。可以发现一行的方案数最多不超过400。
然后将两个可以转移的状态之间两两连边。x可以转移到y表示的意思是x这个状态可以和y这个状态相邻。判断两个状态之间能不能转移显然就是看x和y是不是有某个二进制位同时为1,即只有时,x可以转移到y。
用表示前i行,第行的状态是y的方案数,注意到,第i行的状态可以是y的前提是y这个状态与所给地形之间不存在某个二进制位置i满足且(b表示第i行的地形状态)。。
考虑转移就从所有的转移过来就行了。转移的条件是j这个状态与k这个状态之间有边。
code
/* * @Author: wxyww * @Date: 2020-06-02 19:42:43 * @Last Modified time: 2020-06-02 19:54:25 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int N = 1010,mod = 100000000; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int a[N],ma[N][N],f[20][N],n,m,b[20]; void solve() { int cnt = 0; for(int i = 0;i < (1 << m);++i) { int flag = 0; for(int j = 1;j < m;++j) { if((i >> j & 1) && (i >> (j - 1) & 1)) {flag = 1;break;} } if(!flag) a[++cnt] = i; } memset(b,0,sizeof(b)); for(int i = 1;i <= n;++i) { for(int j = 0;j < m;++j) { int x = read() ^ 1; b[i] |= x << j; } } memset(ma,0,sizeof(ma)); for(int i = 1;i <= cnt;++i) { for(int j = i;j <= cnt;++j) { if(!(a[i] & a[j])) ma[i][j] = ma[j][i] = 1; } } memset(f,0,sizeof(f)); f[0][1] = 1; // cout<<ma[1][2]<<endl; for(int i = 1;i <= n;++i) { for(int j = 1;j <= cnt;++j) { if(a[j] & b[i]) continue; // if(i == 1 && j == 1) puts("!!!"); for(int k = 1;k <= cnt;++k) { if(ma[k][j]) { // if(k == 1 && i == 1) puts("!!!"); f[i][j] += f[i - 1][k],f[i][j] %= mod; } } } } ll ans = 0; for(int i = 1;i <= cnt;++i) ans += f[n][i],ans %= mod; cout<<ans<<endl; } int main() { while(~scanf("%d%d",&n,&m)) solve(); return 0; }