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