SRM722 Lv3 : DominoTiling
作成日：2017.10.13
最終更新日：2017.10.13
問題概要
$H \times W$の$grid$が与えられる。
$'X'$のマスには障害物があり、$'.'$のマスにはない。
障害物がないマスを$2 \times 1$のドミノ(向きは任意)で覆う時の覆い方を求めよ。
制約
$1 \leq H,W \leq 12$
考え方
上の行からドミノの置き方を決めていくことを考える。
ドミノの大きさは$2 \times 1$であるから、ある行のドミノの置き方はその行に隣接する行にのみ依存する。
そこで、行をまたぐ置き方とまたがない置き方で分けて考える。
前者は後者を決めれば$0$通りか$1$通りに定まることから、後者を決めてから下の行に移るということをすれば良さそうである。
これは各行の空きマスの状態それぞれにおいて、その状態になる置き方の数を保持するbitDPで実現できる。
すなわち、ドミノを行をまたがないように左から順に置いていった後、行をまたぐようにドミノを置くことで空きマスを埋めていくことを行ごとに繰り返していけば良い。
計算量は$O(HW2^W)$なので十分高速である。
ソースコード
マクロ等はこちら
class DominoTiling {
int bit[16];
LL dp[16][1<<16];
public:
long long count(vector<string> grid) {
int H = grid.size();
int W = grid[0].size();
repp(i,0,H){
bit[i] = (1<<W)-1;
repp(j,0,W){
if(grid[i][j] == 'X') bit[i] -= (1<<j);
}
}
bit[H] = (1<<W)-1;
dp[0][bit[0]] = 1;
repp(i,0,H){
repp(j,1,W){
repp(k,0,1<<W){
if((k&(1<<(j-1))) == 0 || (k&(1<<j)) == 0) continue;
dp[i][k-(1<<(j-1))-(1<<j)] += dp[i][k];
}
}
if(i==H-1) break;
repp(k,0,1<<W){
if((k&bit[i+1]) != k) continue;
dp[i+1][bit[i+1]^k] = dp[i][k];
}
}
return dp[H-1][0];
}
};解法まとめ
bitDPを行う。
まず行をまたがないようにドミノを左から順に置いていく。(17-22行)
その後、空きマスすべてを下の行にまたがるようにドミノを置くことで埋める。(24-27行)