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]; } };