TopCoder SRM 577 Div1 Hard BoardPainting

問題

hxwのグリッドがある。
最初全てのセルは白で、指定されたセルを全て黒に塗りたい。

一度の操作で、縦または横に一列に連続して並んだ白いセルを選び、
全てを黒に変えることができる。（間に黒が入っていてはだめ）
必要な操作の回数の最小値を求めよ。

制約条件

h, w≦50

方針

指定された全てのセルを、「縦」に塗るか「横」に塗るかを決めるとコストが一意に決まる。
すなわち、「縦」のセルが上下方向で「縦」のセルに隣接してないときにコスト+1,
「横」のセルが上下方向で「横」のセルに隣接していないときコスト+1,とする。

列の両端でコストが1ずつかかるので、求めるコストはこのコストの半分。

で、この最小値は最小カットを使えば求まる。
s, tおよび各セルを頂点とするグラフを作る。
塗るべきセルcを縦として使う場合、cに対応する頂点をs-tカットのs側に含めるとする。
横として使う場合、cに対応する頂点をt側に含めるとする。

縦として使うとき、上のセルも縦じゃない場合＝カットが生じる場合なので、
そこに容量1の辺を張る。下方向についても同様。
横として使うとき、左のセルも横じゃない場合＝カットが生じる場合なので、
そこに容量1の辺を張る。右方向についても同様。

このようにして作ったグラフで、s-t間の最大流を求めれば、
max-flow min-cut定理から、それが最小カットである。

ソースコード

class BoardPainting {
	public:
	int minimalSteps(vector <string> target) {
		
		int h = target.size(), w = target[0].size();
		int s = h * w, t = h * w + 1;
		flowGraph g(h * w + 2);
		
		rep(i, h) rep(j, w) if(target[i][j] == '#'){
			int v = 0, ho = 0;
			
			for(int d = -1; d < 2; d += 2){
				if(i + d < 0 || i + d >= h || target[i + d][j] == '.') v++;
				else g.add(i * w + j, (i + d) * w + j, 1);
				if(j + d < 0 || j + d >= w || target[i][j + d] == '.') ho++;
				else g.add(i * w + j, i * w + (j + d), 1);
			}
			g.add(s, i * w + j, v);
			g.add(i * w + j, t, ho);
		}
		return g.max_flow(s, t) / 2;
	}
};