题意
农场主John新买了一块长方形的新牧场，这块牧场被划分成
M
M
M行
N
N
N列
(
1
≤
M
≤
12
;
1
≤
N
≤
12
)
(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)
(1≤M≤12;1≤N≤12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
输入格式
第一行：两个整数
M
M
M和
N
N
N，用空格隔开。
第2到第
M
+
1
M+1
M+1行：每行包含
N
N
N个用空格隔开的整数，描述了每块土地的状态。第
i
+
1
i+1
i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。
输出格式
一个整数，即牧场分配总方案数除以100,000,000的余数。
详细思路及代码逻辑
建议先做一下炮兵阵地，双倍经验。拿到题先估计，这是一个状态压缩的动归，为什么呢？因为数据很动归，而且矩阵的元素非0即1，很适合状态压缩。那么怎么进行下去呢，我们主要由以下几个问题。
- 对谁进行状态压缩？
- 动态规划的思路，转移方程是什么？
- 最终结果如何得到？
首先我们考虑对哪个元素进行压缩，对全局的矩阵嘛?不合适，太大了，就经验来看，矩阵形式的DP一般都压缩每一行的状态，然后一行一行遍历，我们不妨试一试使用dp[i][s]表示，到第i行，状态为s时可能的种植方案数目，那么我们可以得到这样一个递推关系式
d
p
[
i
]
[
s
]
=
∑
k
=
0
m
d
p
[
i
−
1
]
[
k
]
dp[i][s]=\sum_{k=0}^{m}dp[i-1][k]
dp[i][s]=k=0∑mdp[i−1][k]
其中
m
m
m是所有与
s
s
s不冲突而且可以在
i
−
1
i-1
i−1行使用的状态。那么我们至少需要如此一个for循环
for (int i = 1; i < M; i++) {//遍历第2-M行
//转移条件
for (int k = 0; k < cnt; k++) {//遍历第i行的所有状态
//转移条件
for (int m = 0; m < cnt; m++) {
//转移条件
dp[i][k] = (dp[i][k] % mod + dp[i - 1][m] % mod) % mod;
}
}
}
cnt是可用的状态总数目，10个位置的话总共也就是1024，不过我们会对他进行一步优化，使其远远比1024小（之后再说）。我们先填充这些转移条件，有什么条件呢？
- 不能种在不肥沃的土地上！比如第一行是
101，在输入时我们将不肥沃的土地转化为1，其余视为0，那么表示为010，此时我们的状态是110（1表示种了，0没种），可以看到只要我们将二者按位与，如果结果是1，那么肯定在不肥沃的土地上种植了，该状态不可以用。tips：使用一个数组mmap保存所有行的土地状况。
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
int a; cin >> a;
if (a == 0) mmap[i] |= (1 << j);
}
}
- 上一行和这一行不能有相邻节点。同样我们使用按位与操作，如果两行在某个位置上都种植了，比如
1100和1000，那么按位与的结果一定是1.
- 同一行也不能有相邻节点。对这个要求，我们可以对每一行能选择的状态进行预处理，左右有相邻元素的状态可以抛掉，只保留可以用的状态（不仅减小内存，而且加快速度）
s[0] = 0;
for (int i = 1; i < (1 << N); i++) {
if (i&(i << 1) || i & (i >> 1))continue;//左右有相连的种植土地
s[cnt++] = i;
}
好我们现在补全for循环
for (int i = 1; i < M; i++) {//遍历第2-M行
for (int k = 0; k < cnt; k++) {//遍历第i行的所有状态
//k状态和i的地形冲突
if (mmap[i] & s[k]) continue;
for (int m = 0; m < cnt; m++) {
//m状态与i-1行的地形冲突或者m状态与k状态有临边
if ((mmap[i - 1] & s[m]) || (s[m] & s[k])) continue;
dp[i][k] = (dp[i][k] % mod + dp[i - 1][m] % mod) % mod;
}
}
}
然后还有一件事别忘了，就是第一行需要特判处理，每个可行的方案基础值都是1，等等？不是方案总数嘛？为什么用1来替代—因为我们会遍历所有的情况，再回顾递推公式
d
p
[
i
]
[
s
]
=
∑
k
=
0
m
d
p
[
i
−
1
]
[
k
]
dp[i][s]=\sum_{k=0}^{m}dp[i-1][k]
dp[i][s]=∑k=0mdp[i−1][k]，只要是可能的组合我们都会直接加上，对1001这种形式，1000和0001的组合我们都已经遍历过了，因此只需要将num[9（1001）]赋值为1即可。
for (int i = 0; i < cnt; i++) {
if (mmap[0] & s[i])continue;
dp[0][i] = 1;
}
最后，把第N行的所有可能结果加起来就是我们需要的结果了。
int res = 0;
for (int i = 0; i < cnt; i++) res = (res%mod + dp[M - 1][i] % mod) % mod;
cout << res << endl;
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX 15
#define mod 100000000
int M, N, cnt = 1, mmap[MAX];
//dp[i][s]:遍历到第i行，状态为s时的种植方案总数，num[s]：状态s有几种种植方案, s:可用状态集合
int dp[MAX][1024], num[1024], s[1024];
int count1(int k) {
int ans = 0;
while (k > 0) {
ans++;
k -= (k&(-k));
}
return ans;
}
int main() {
cin >> M >> N;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
int a; cin >> a;
if (a == 0) mmap[i] |= (1 << j);
}
}
s[0] = 0;
for (int i = 1; i < (1 << N); i++) {
if (i&(i << 1) || i & (i >> 1))continue;//左右有相连的种植土地
s[cnt++] = i;
}
for (int i = 0; i < cnt; i++) {
if (mmap[0] & s[i])continue;
dp[0][i] = 1;
}
for (int i = 1; i < M; i++) {//遍历第2-M行
for (int k = 0; k < cnt; k++) {//遍历第i行的所有状态
//k状态和i的地形冲突
if (mmap[i] & s[k]) continue;
for (int m = 0; m < cnt; m++) {
//m状态与i-1行的地形冲突或者m状态与k状态有临边
if ((mmap[i - 1] & s[m]) || (s[m] & s[k])) continue;
dp[i][k] = (dp[i][k] % mod + dp[i - 1][m] % mod) % mod;
}
}
}
int res = 0;
for (int i = 0; i < cnt; i++) res = (res%mod + dp[M - 1][i] % mod) % mod;
cout << res << endl;
}
