TopCoder SRM 575 Div1 Hard TheTilesDivOne

問題

h x wのチェス盤がある。
座標(i, j)が、(i + j) % 2 = 0 を満たすマスは黒で、そうでないマスは白である。
いくつかのマスには障害物が置かれている。

チェス盤に、ちょうど３マス分のサイズのL字のブロックを置く。

• ブロックは、角の部分が黒いマスに置かれる。
• 残りの二つの部分は白いマスに置かれる。
• ブロック同士が重なったり、ブロックがチェス盤からはみ出たりしてはならない。
• ブロックが、障害物のマスと重なってはならない。

上の条件を満たすように置くことのできるブロックの数の最大値はいくつか、求めよ。

制約条件

h, w≦50

方針

次のようなグラフを作って最大流を求める。

置かれたL字のブロックは、黒いマスから、横と縦に白いマス二つにつながっている。
なので、黒いマスから白いマス二つに辺を張りたい。
このままだと向きが謎だが、白いマスをi % 2 = 0のものと、i % 2 = 1のものにわけると、
一方からフローが出て、一方へ入る、としてよいことがわかる。

なので、i % 2 = 0の白いマスにはソースから流量1の辺を張り、
そこから周りの黒いマスへ流量1の辺を張る。
i % 2 = 1の白いマスは、シンクへの流量1の辺を張る。
黒いマスからは、周りのシンクへつながる白いマスに流量1の辺を張る。

このままだと、1つのマスに2以上のフローが流れてしまうので、
一つの頂点をIN, OUTに分裂させて、IN→OUTに流量1の辺を張って、
一つの頂点に1のフローしか流れないようにする。

以上のグラフの最大流を求めればよい。

ソースコード

class TheTilesDivOne {
	public:
	int find(vector <string> board) {
		int h = board.size(), w = board[0].size();
		int s = h * w * 2, t = s + 1;
		
		flowGraph g(t + 1);
		rep(i, h) rep(j, w) if(board[i][j] == '.'){
			
			g.add((i * w + j) * 2, (i * w + j) * 2 + 1, 1);
			
			if((i + j) % 2 == 0){
				rep(d, 4){
					const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
					int y = i + dy[d], x = j + dx[d];
					if(y < 0 || x < 0 || y >= h || x >= w || board[y][x] == 'X') continue;
					if(y % 2 == 1) g.add((i * w + j) * 2 + 1, (y * w + x) * 2, 1);
				}
			}
			else if(i % 2 == 0){
				g.add(s, (i * w + j) * 2, 1);
				rep(d, 4){
					const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
					int y = i + dy[d], x = j + dx[d];
					if(y < 0 || x < 0 || y >= h || x >= w || board[y][x] == 'X') continue;
					g.add((i * w + j) * 2 + 1, (y * w + x) * 2, 1);
				}
			}
			else{
				g.add((i * w + j) * 2 + 1, t, 1);
			}
		}
		return g.max_flow(s, t);
	}
};