POJ - 3254 Corn Fields 狀態壓縮

POJ - 3254 Corn Fields 狀態壓縮

題目大意：有一個網格，網格上面有草地和荒地，現在要在這個方格上面放士兵，士兵只能放在草地上，不能放在荒地上，且士兵不能兩兩相連，問有多少種放士兵的方式(也可以一個士兵都不放)

解題思路：這題和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;
}