题目大意：有一个网格，网格上面有草地和荒地，现在要在这个方格上面放士兵，士兵只能放在草地上，不能放在荒地上，且士兵不能两两相连，问有多少种放士兵的方式(也可以一个士兵都不放)
解题思路：这题和POJ - 1185 炮兵阵地类似，是简单版的，就不详说了，poj有点坑啊，我的数组开小了，给出的是WA，找了半天没找到。。。
现在给出1185的链接
这里写链接内容
#include
#include
#include
using namespace std; #define maxn 20 #define maxm 5010 #define mod 100000000 int R, C; int row[maxn], state[maxm], dp[maxn][maxm]; int cnt; void init() { memset(row, 0, sizeof(row)); memset(dp, 0, sizeof(dp)); int t; for(int i = 0; i < R; i++) for(int j = 0; j < C; j++) { scanf(%d, &t); if(!t) row[i] |= (1 << j); } cnt = 0; for(int i = 0; i < (1 << C); i++) { if(i & (i << 1)) continue; state[cnt++] = i; } for(int i = 0; i < cnt; i++) { if(state[i] & row[0]) continue; dp[0][i] = 1; } for(int r = 1; r < R; r++) for(int i = 0; i < cnt; i++) { if(state[i] & row[r]) continue; for(int j = 0; j < cnt; j++) { if(state[j] & row[r-1]) continue; if(state[i] & state[j]) continue; dp[r][i] = (dp[r-1][j] + dp[r][i]) % mod; } } } int solve() { int ans = 0; for(int i = 0; i < cnt; i++) ans = (ans + dp[R-1][i]) % mod; return ans; } int main() { scanf(%d%d, &R, &C); init(); printf(%d , solve()); return 0; }
?