题目描述 Farmer John新买了一块长方形的牧场，这块牧场被划分成M列N行(1<=M<=12; 1<=N<=12)，每一格都是一块正方形的土地。FJ打算在牧场上的某几格土地里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当的贫瘠，不能用来放牧。并且，奶牛们喜欢独占一块草地的感觉，于是FJ不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。当然，FJ还没有决定在哪些土地上种草。 作为一个好奇的农场主，FJ想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择。当然，把新的牧场荒废，不在任何土地上种草，也算一种方案。请你帮FJ算一下这个总方案数。 输入
第1行: 两个正整数M和N，用空格隔开第2…M+1行: 每行包含N个用空格隔开的整数，描述了每块土地的状态。输入的第i+1行描述了第i行的土地。所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块地上不适合种草 输出第1行: 输出一个整数，即牧场分配总方案数除以100,000,000的余数 样例输入 2 3 1 1 1 0 1 0 样例输出 9思路：先将第一行的所有状态初始化，接下来每一行的状态都需要受到其上一行的状态限制。因此要先处理第一行的状态，再依次处理下面的状态。但这题还要受到草地本身情况的限制，因此我多加了一个状态本身与草地情况是否有冲突的判断。
代码：
#include<bits/stdc++.h> #define ll long long using namespace std; const ll N=1e8; int n,m; int a1[15][15],a[15]; int fla[4100];//用于记录草地本身是否可行 //第一维代表草地行数，第二维代表草地的状态 ll dp[15][4100]; //用于草地情况和此种状态是否有冲突的判断函数 int judge(int state,int line) { for(int i = 1; i <= m; i++) { //若草地本身的状态为0，则不能种草 if(a1[line][i]==0) { //若种了草，则此种状态不可取 if((state&(1<<(i-1)))>0) return 0; } } return 1; } void first_line() { for(int i = 0; i < (1<<m); i++) { //此种状态没有相邻的两块草地 if(!(i&(i<<1))) { fla[i]=1; //此种状态没有将草种在荒芜的地上 if(judge(i,1)) { dp[1][i]++; } } } return ; } int main() { cin>>n>>m; //输入每行草地的情况 for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { //倒序储存，方便后续的验证 cin>>a1[i][m-j+1]; } //第一行草地只受自身草地状态和排列限制 //因此单独考虑 first_line(); for(int i = 2;i <= n; i++ ) for(int j = 0; j < (1<<m); j++) { //此种状态本身就不可取 if(!fla[j]) continue; //此种状态与草地有冲突不可取 if(!judge(j,i)) continue; for(int k = 0; k < (1<<m);k++) { //此种状态本身不可取 if(!fla[k]) continue; //上下两行有冲突 if((k&j)>0) continue; //满足一切要求，则可以加上这种情况的数量 dp[i][j]+=dp[i-1][k]; dp[i][j]%=N; } } //累加每种状态的情况数 ll ans=0; for(int i = 0; i < (1<<m); i++) { ans+=dp[n][i]; ans%=N; } cout<<ans; return 0; }