PKU 3254:Corn Fields

問題文 : http://poj.org/problem?id=3254
概要 : 0のところは必ず0で, 1のところは0または1にできる. このとき, 1が隣接しないようなマスの作り方は何通りあるか.

解法とか問題の種類とか:
簡単なbitDPです.
今見ている場所より上がvalidで, 下は今から決める, という考え方で, 考えるべき空間がグッと減るのがbitDPの良い所だなーと思います.

この問題は右と上に隣接することを念頭に置きながら考えないと行けないのですが, 今見ている場所が右端だとすると、右隣が無いことに注意しましょう.

#include <cstdio>
#include <cstring>

#define MOD (100000000)

typedef long long ll;

using namespace std;

int W, H;
int mask;

ll memo[144][1 << 12];
int isok[12][12];

ll count(int pos, int bit)
{
    int ny = pos / W, nx = pos % W;
    ll res;
    
    if (pos == W * H){
        return (1);
    }
    
    res = memo[pos][bit];
    if (res == -1){
        res = 0;
        if (!isok[ny][nx]){
            res = (res + count(pos + 1, (bit << 1) & mask)) % MOD;
        }
        else {
            res = (res + count(pos + 1, (bit << 1) & mask)) % MOD;
            if (!(nx != 0 && bit & 1) && !((bit >> (W - 1)) & 1)){
                res = (res + count(pos + 1, ((bit << 1) | 1) & mask)) % MOD;
            }
        }
    }
    
    return (memo[pos][bit] = res);
}

int main()
{
    scanf("%d %d", &H, &W);
    
    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            scanf("%d", &isok[i][j]);
        }
    }
    
    mask = (1 << W) - 1;
    memset(memo, -1, sizeof(memo));
    
    printf("%lld\n", count(0, 0));
    
    return (0);
}