这道题还是很明显的状压DP。毕竟数据范围很小。
然后此题和前面的互不侵犯，炮兵阵地这两道题还是非常相似的。我们使用dp[i][j]表示枚举到第i行，当前行状态为j的方案数，之后直接向下一行转移就可以啦。
然后因为这道题要求的是方案数，而且并没有要求种多少草，所以没有必要记录一共有多少块草，直接DP就可以，因为所有的方案数肯定都会被计算过的。
同样的，先处理出所有不和情况的状态，在合法状态中dp就可以，方法可以参照炮兵阵地那道题。
然后别把mn搞反……（无辜爆0）
看代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 50005; const int mod = 100000000; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int m,n,shape[15],sum[5000],s[5000],dp[15][5000],tot,a,ans; void init() { rep(i,0,(1<<n)-1) { if((!(i&(i<<1))) && (!(i&(i>>1)))) { s[++tot] = i; if(s[tot] & shape[1]) continue; dp[1][tot] = 1; } } } int main() { //freopen("a.in","r",stdin); m = read(),n = read(); rep(i,1,m) rep(j,1,n) { a = read(); if(!a) shape[i] += (1<<(n-j)); } init(); rep(i,2,m) rep(j,1,tot) { if(s[j] & shape[i]) continue; rep(p,1,tot) { //if(s[p] & shape[i]) continue; if(s[j] & s[p]) continue; dp[i][j] += dp[i-1][p],dp[i][j] %= mod; } } rep(i,1,tot) ans += dp[m][i],ans %= mod; printf("%d ",ans); return 0; }