TopCoder Open 2014 Round1B Medium WolvesAndSheep
問題
hxwのグリッドがあり、それぞれ'W'(狼)または'S'(羊)か'.'(何もいない)のいずれか。
ここに仕切りを入れて、わかれた区画それぞれについて、狼と羊が同時にいることがないようにしたい。
仕切りは、好きな二列の間、または好きな二行の間に入れることができる。
必要な仕切りの個数の最小値を求めよ。
制約条件
h, w≦16
方針
まず縦向きの仕切りの入れ方を決め打ちする。(2^(w-1)通り)
そしたら次は横向きの仕切りの個数を、
dp[何行まで見たか][最後に入れた仕切りの位置] := 仕切りの個数の最小値
により求めればよい。
更新のときに、一つの区画に狼と羊が同時に入る状態は捨てるようにする。
ソースコード
class WolvesAndSheep { public: int getmin(vector <string> field) { int h = field.size(), w = field[0].size(); int ans = inf; rep(tate, 1 << w - 1){ vector<vi> idx; vi cur; rep(i, w){ cur.pb(i); if((tate & 1 << i) || i == w - 1){ idx.pb(cur); cur.clear(); } } int dp[20]; rep(i, h + 1) dp[i] = inf; dp[0] = 0; rep(i, h) if(dp[i] < inf){ vi sheep(idx.size()), wolf(idx.size()); for(int k = i; k < h; k++){ bool ng = 0; rep(l, idx.size()) rep(m, idx[l].size()){ if(field[k][idx[l][m]] == 'S') sheep[l]++; if(field[k][idx[l][m]] == 'W') wolf[l]++; } rep(l, idx.size()) if(sheep[l] && wolf[l]) ng = 1; if(ng) break; dp[k + 1] = min(dp[k + 1], dp[i] + 1); } } ans = min(ans, __builtin_popcount(tate) + dp[h] - 1); } return ans; } };