玉米田（HG 2018.4.22 T2）

### 【题目描述】 FJ 购买了一处肥沃的矩形牧场，分成 M N(1 M 12; 1 N 12) 个格子。他想在那里的一些格子中种植美味的玉米。遗憾的是，有些格子区域的土地是贫瘠的，不能耕种。 精明的 FJ 知道奶牛们进食时不喜欢和别的牛相邻，所以一旦在一个格子中种植玉米，那么他就不会在相邻的格子中种植，即没有两个被选中的格子拥有公共边。他还没有最终确定哪些格子要选择种植玉米。 作为一个思想开明的人，FJ 希望考虑所有可行的选择格子种植方案。由于太开明，他 还考虑一个格子都不选择的种植方案！请帮助 FJ 确定种植方案总数。 ### 【输入格式】 第一行包括两个用空格分隔的整数 M 和 N。 接下来的 M 行，每行 N 个数，描述了每行格子是否可以种植的情况（1 表示肥沃的、 适合种植，0 表示贫瘠的、不可种植）。 ### 【输出格式】 输出一个整数，表示 FJ 可选择的方案总数 mod 108 的结果。 ### 【输入输出样例】 cowfood.in 2 3 1 1 1 0 1 0 cowfood.out 9 ### 【 数据规模与约定 】 对于 60% 的数据，1 ≤ M，N ≤ 6 对于 100% 的数据，1 ≤ M，N ≤ 12 ------------ ------------ ------------ 同Mondriaan的梦（HG 2018.4.15 试题1 T3） 状压DP一道。用f[i][j]表示第i行状态为j时的方案数。j依然是个二进制数 f[i][j]通过f[i-1][k]转移过来，k是i-1行合法的所有状态（即不和j冲突） 注意：在dfs前先要判断枚举的j是否合法。 ```cpp #include<map> #include<set> #include<list> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define MOD 100000000 int n,m; int a[13][13],f[13][1<<13]; void dfs(int i,int j,int p,int s) { if(p>m) return; if(p==m) { f[i][j]=(f[i][j]+f[i-1][s])%MOD; return; } if((j & (1 << p))==0) { dfs(i,j,p+1,s); dfs(i,j,min(m,p+2),s | (1<<p)); //p+2：保证相邻的两位不会同时种植，种了第p位，p+1必然是不种，可直接跳过 } else dfs(i,j,p+1,s); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); f[0][0]=1; for(int i=1;i<=n+1;i++) for(int j=0;j< (1<<m) ;j++) { int flag=1; for(int k=0;k<m;k++) { if((j & (1<<k)) && a[i][k+1]==0)//如果第k位要种，但是土地贫瘠，不行 { flag=0; break; } if((j & (1<<k)) && (j & (1<<(k+1))))//如果有相邻的两位要种，不行 { flag=0; break; } } if(flag) { dfs(i,j,0,0); } } printf("%d",f[n+1][0]); fclose(stdin); fclose(stdout); return 0; } ``` 经过这一道题得出的结论：括号一定不能少加，千万不要为了压行而压行，会死的很惨的