POJ-3254 : Corn Fields

問題概要

H*W(H,W<12)のグリッドグラフ上で独立集合の個数を求める問題。

解法

各マスについて列の状態を保持しながらビットdpする。

時間

30分かかった。遅い。入力の0と1を間違えてしかも2回も間違えた。入力読み込んだ時点で自分に分かりやすいようフリップしとくべきだった。

acceptされたコード

#include <cstdio>
using namespace std;

const int MOD = (int)( 1e8 );

const int MAX_N = 12;

int H, W;
int board[MAX_N][MAX_N];
int ways[MAX_N+1][MAX_N][1<<MAX_N];

void init() {
	scanf("%d%d", &H, &W);
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			scanf("%d", &board[i][j]);
		}
	}
}

int solve() {
	int t = 0;
	for (int i = 0; i < W; ++i) {
		t |= ((board[0][i]^1) << i);
	}
	ways[0][0][t] = 1;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			int ny = j == W - 1 ? i + 1 : i, nx = j == W - 1 ? 0 : j + 1;
			for (int blocked = 0; blocked < 1<<W; ++blocked) {
				
				{
					int nbit = blocked &~ (1<<j);
					if (i == H - 1 || board[i+1][j] == 0) {
						nbit |= (1<<j);
					}
					ways[ny][nx][nbit] = (ways[ny][nx][nbit] + ways[i][j][blocked]) % MOD;
				}

				
				if (!((blocked>>j)&1)) {
					int nbit = blocked | (1<<j);
					if (j < W - 1) {
						nbit |= (1<<(j + 1));
					}
					ways[ny][nx][nbit] = (ways[ny][nx][nbit] + ways[i][j][blocked]) % MOD;
				}
			}
		}
	}

	return (int)ways[H][0][(1<<W)-1];
}

int main() {
	init();
	printf("%d\n", solve());

	return 0;
}