题意：
John 有一个豪华的M*N个格子组成的新牧场 他想种美味的玉米 但是有些位置不能种 而且他种地不选择相邻的格子 求所有可能的种地方法 （不种也算一种选择）
输入：第一行M和N， 第二行M*N地图，1代表该方格可以种地 0代表不可以种地输出：方法数 % 100000000.开始读题读错（ no two chosen squares share an edge.）。。。
详细注释代码：
/*********************************************************Problem: 3254 User: G_loryMemory: 860K Time: 16MSLanguage: G++ Result: Accepted*********************************************************/#include#include 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<
第二次做的代码（毕竟第一次是照着别人的代码写的）
/***************************************************************Memory: 880 KB Time: 0 MSLanguage: G++ Result: Accepted****************************************************************/#include#include #include 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;}