TopCoder SRM 449 Div1 Medium HexagonalBattlefield

問題

hex座標で表されるNxNのフィールドがある。
フィールドのいくつかのマスは埋まっている。


埋まっていないマス全てに、1x2のブロックを敷き詰める。
ブロックは重なったり、フィールドの外に出たりしてはならない。
ブロックの置き方の場合の数をmod 2 * 10^9 + 11で求めよ。

制約条件

N≦15

方針

hex座標を座標変換して普通の二次元グリッドにする。
このグリッド上で、(x, y)とつながる点は(下方向は)(x + 1, y), (x, y + 1), (x + 1, y + 1)


ここで、一列と1マスを覚えるDPをすればいい。

ソースコード

const int mod = (int)2e9 + 11;
bool ob[20][20];
ll dp[16][1<<15][2];

class HexagonalBattlefield {
	public:
	int countArrangements(vector <int> X, vector <int> Y, int N) 
	{
		memset(ob, 0, sizeof(ob));
		memset(dp, 0, sizeof(dp));
		
		int n = 2 * N - 1;
		
		rep(i, X.size()){
			int y = N - 1 - Y[i], x = X[i] + y;
			ob[y][x] = 1;
		}
		
		rep(i, N) rep(j, N - i - 1){
			ob[i][n - j - 1] = 1;
			ob[n - i - 1][j] = 1;
		}
		
		dp[0][0][0] = 1;
		rep(i, n){
			rep(j, n) rep(b, 1 << n) rep(a, 2){
				
				bool f1 = !(b >> j & 1) && !ob[i][j];
				bool f2 = j < n - 1 && !(b >> j + 1 & 1) && !ob[i][j + 1];
				bool f3 = i < n - 1 && !ob[i + 1][j] && !a;
				bool f4 = i < n - 1 && j < n - 1 && !ob[i + 1][j + 1];
				
				if(!f1){
					int nb = b & ~(1 << j) | a << j;
					(dp[j + 1][nb][0] += dp[j][b][a]) %= mod;
					continue;
				}
				
				if(f2){
					int nb = b & ~(1 << j) & ~(1 << j + 1) | a << j;
					(dp[j + 2][nb][0] += dp[j][b][a]) %= mod;
				}
				if(f3){
					int nb = b | 1 << j;
					(dp[j + 1][nb][0] += dp[j][b][a]) %= mod;
				}
				if(f4){
					int nb = b & ~(1 << j) | a << j;
					(dp[j + 1][nb][1] += dp[j][b][a]) %= mod;
				}
			}
			rep(b, 1 << n) dp[0][b][0] = dp[n][b][0];
			for(int j = 1; j <= n; j++) rep(b, 1 << n) rep(a, 2) dp[j][b][a] = 0;
		}
		return dp[0][0][0];
	}
};