题意：
John 有一个豪华的M*N个格子组成的新牧场 他想种美味的玉米 但是有些位置不能种 而且他种地不选择相邻的格子 求所有可能的种地方法 （不种也算一种选择）
输入：第一行M和N， 第二行M*N地图，1代表该方格可以种地 0代表不可以种地
输出：方法数 % 100000000.
开始读题读错（ no two chosen squares share an edge.）。。。
详细注释代码：
/*********************************************************
Problem: 3254 User: G_lory
Memory: 860K Time: 16MS
Language: G++ Result: Accepted
*********************************************************/
#include <cstdio>
#include <cstring> const int N = 13;
const int MAX = 1 << N;
const int MOD = 100000000; int st[MAX]; //根据每一行的列数，存储可能存在的状态
int map[MAX]; //存储原地图每一行的状态
int dp[N][MAX]; //对于每一行，每个状态可能的情况 bool judge(int x) //通过移位然后与运算判断一状态合不合法
{ //例如 10110 移位之后是
return x & (x << 1); //。。 01100 不为0证明至少有一位相邻
} bool judge(int a, int b) //通过与原地图与运算判断该状态是否合法
{
return map[a] & st[b];
} int main()
{
//freopen("in.txt", "r", stdin);
int m, n;
while (~scanf("%d%d", &n, &m)){
memset(map, 0 ,sizeof (map));
memset(st, 0 ,sizeof (st));
memset(dp, 0 ,sizeof (dp)); int x;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &x);
if (!x) map[i] += 1 << (j - 1); //地图中存的是0的位置，这样就可以和其他状态直接与
}
}
int limit = 1 << m;
int cnt = 0;
for (int i = 0; i < limit; ++i) { //m位那么1<<m种状态，判断其中哪些状态是合法的
if (!judge(i))
st[cnt++] = i; //最终有cnt种合法状态
} for (int i = 0; i < cnt; ++i) { //第一行，合法那么该状态是一种可能
if (!judge(1, i))
dp[1][i] = 1;
} for (int i = 2; i <= n; ++i) { //第2-n行
for (int j = 0; j < cnt; ++j) {
if (judge(i, j)) continue; //如果该状态不满足地图继续
for (int k = 0; k < cnt; ++k) { //所有与该状态不冲突的上一行状态可能情况想加
if (!(st[j] & st[k])) dp[i][j] += dp[i - 1][k];
}
}
} int ans = 0;
for (int i = 0; i < cnt; ++i)
ans = (ans + dp[n][i]) % MOD;
printf("%d\n", ans);
}
return 0;
}
第二次做的代码（毕竟第一次是照着别人的代码写的）
/***************************************************************
Memory: 880 KB Time: 0 MS
Language: G++ Result: Accepted
****************************************************************/
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std; typedef long long ll; // (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) const int M = 12;
const int N = 12;
const int MAXN = 1 << N;
const int MOD = 100000000; int mp[M];
int dp[M][MAXN]; int m, n; bool judge(int i, int j)
{
return !(j & (j << 1)) && !(~mp[i] & j);
} void solve()
{
for (int i = 0; i < 1 << n; ++i) {
if (judge(0, i)) dp[0][i] = 1;
} for (int i = 1; i < m; ++i) {
for (int j = 0; j < 1 << n; ++j) {
if (judge(i, j)) {
int res = 0;
for (int k = 0; k < 1 << n; ++k) {
if (!(j & k)) {
res = (res + dp[i - 1][k]) % MOD;
}
}
dp[i][j] = res;
}
}
} int res = 0;
for (int i = 0; i < 1 << n; ++i)
res = (res + dp[m - 1][i]) % MOD; printf("%d\n", res);
} int main()
{
while (scanf("%d%d", &m, &n) != EOF) {
memset(dp, 0, sizeof dp);
for (int i = 0; i < m; ++i) {
int temp;
int res = 0;
for (int j = 0; j < n; ++j) {
scanf("%d", &temp);
res += temp * (1 << j);
}
mp[i] = res;
}
solve();
}
return 0;
}