TopCoder SRM 594 Div1 Medium FoxAndGo3

問題

nxnのグリッドに白石'o'と黒石'x'が置かれている。
何も置かれていない場所は'.'


辺を共有する白石はひとかたまりとみなす。
ひとかたまりの白石が、何も置かれていない場所に隣接していない状態になると、
その白石は全て'.'に変わる。

黒石を好きなだけ置くことができるとき、
グリッドの空いているマスの個数は最大いくつにできるか求めよ。
置かれている黒石や、置いた黒石はなくなることはない。

制約条件

n≦50
初期状態で、白石のかたまりは必ずどこかの'.'と隣接している。

方針

最小カット。
フローグラフを以下のように構成する。


'o'に対応する頂点:その頂点がs-tカットのs側に含まれるとき「そのマスの'o'を取り除く操作をする」という意味の頂点
'.'に対応する頂点:その頂点がs-tカットのs側に含まれるとき「そのマスに'x'を置く操作をする」という意味の頂点


最小カットにしたいので、「損を最小化する」と考える。
すなわち、最大値の上界から、必要最小の損を引いて、利益の最大値を出す。

'o'を取り除く操作に関して、まずは答えに1を足しておく。
操作をしないと、コスト1損するので、
s側に含まれないとき(sとの辺を切ったとき)に1損するようにする。
すなわち、sからその頂点に流量1の辺を張る。


'.'に石を置く操作に関しても、まず答えに1を足す。
操作をするときにコスト1損するので、
s側に含まれるとき(tとの辺を切ったとき)1を損するようにする。
すなわち、その頂点からtへ流量1の辺を張る。


そして、ひとつの'o'の操作を行うためには、その周囲の'.'を全部埋めなければならない。
つまり、'o'の操作に対して絶対に一緒に行わなければならない'.'が存在する。
ここがカットされないように、'o'から'.'へ流量無限大の辺を張る。
(すると最小カットではカットされなくなる)


このようにして作ったグラフでs-t最大フローを求めれば、
最小カットに等しいので、最初に増やしておいた答えから損を引けば答えが求まる。

ソースコード

struct FoxAndGo3{
	int h, w;
	bool v[50][50];
	vector<string> board;
	void dfs(int y, int x, vi &res){
		rep(d, 4){
			const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
			int ny = y + dy[d], nx = x + dx[d];
			if(ny < 0 || nx < 0 || ny >= h || nx >= w || v[ny][nx]) continue;
			v[ny][nx] = 1;
			if(board[ny][nx] == 'o') dfs(ny, nx, res);
			if(board[ny][nx] == '.') res.pb(ny * w + nx);
		}
	}
	
	int maxEmptyCells(vector <string> board){
		h = board.size(), w = board[0].size();
		this->board = board;
		int ans = 0;
		int s = h * w, t = s + 1;
		flowGraph g(h * w + 2);
		
		rep(i, h) rep(j, w){
			if(board[i][j] == 'o'){
				ans++;
				g.add(s, i * w + j, 1);
				memset(v, 0, sizeof(v));
				vi v;
				dfs(i, j, v);
				rep(k, v.size()) g.add(i * w + j, v[k], inf);
			}
			if(board[i][j] == '.'){
				ans++;
				g.add(i * w + j, t, 1);
			}
		}
		return ans - g.max_flow(s, t);
	}
};