kmjp's blog

競技プログラミング参加記です

TopCoder SRM 625 Div1 Medium BlockTheBlockPuzzle

うーん、本番中に解けなかったのが惜しい。
http://community.topcoder.com/stat?c=problem_statement&pm=12551

問題

2次元グリッド上を、1x1x2の直方体を転がす。
ただし、図の通り長さ2の辺を中心に転がすことはできない。

グリッド上は、通常マス・穴・開始マス・ゴールマスがある。
当然穴のマスに直方体を置くことはできない(倒れた状態の直方体なら、接地面2マスのうち片方穴でなければ置くことができる)

任意の開始マスに直方体を立てた状態から、ゴールマスに直方体を建てることができないよう、穴を増やしたい。
最小何個穴を増やせばゴールマスに直方体を建てることができなくなるか。

解法

開始マスからゴールマスに至る経路をすべてつぶす問題なので、グラフの最小カットを求める問題と言い換えることができる。
もちろん、最小カット最大フロー定理より、うまいフローを作って最大フローを求めればよい。

長さ2の辺で直方体を転がせないため、直方体が立つのは開始マスからX座標およびY座標の移動距離が3の倍数の時のみとなる。
そこで以下のようにグラフを作る。

$及び*はゴールとのX,Y座標の差が3の倍数となるセルである。
このようなセルに対しては2つの頂点を取り、容量1の辺でつなぐ。
これはこのセルに穴を配置するとそこは移動できなくなる、という状態を再現するためである。

それらの間をつなぐ--や||は2マスで1個の頂点とし、左右や上下のセルと連結する。
この際の辺の容量は2マス中の空白マスの数である。

なお、いずれの頂点に置いても、対応するセルに1個以上開始マスがある場合、そこは穴が配置できず塞ぐことはできないので、仮置きで2500とか大き目の容量を設定しておけばよい。

........
.$--*--*
.|..|..|
.|..|..|
.*--*--*
.|..|..|
.|..|..|
.*--*--*

あとはsourceから各開始マスに容量1ずつ辺を張り、ゴールマスに至る最大フローを求めればよい。

class MaxFlow {
public:
	struct edge { int to, capacity, reve;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[MV];
	
	void init() { for(int i=0;i<MV;i++) E[i].clear();}
	MaxFlow() {init();}
	void add_edge(int x,int y, int cap) {
		E[x].push_back((edge){y,cap,(int)E[y].size()});
		E[y].push_back((edge){x,0, (int)E[x].size()-1}); /* rev edge */
	}
	
	int dfs(int from,int to,int cf) {
		int i,tf;
		if(from==to) return cf;
		vis[from]=1;
		FOR(i,E[from].size()) {
			edge& e=E[from][i];
			if(vis[e.to]==0 && e.capacity>0 && (tf = dfs(e.to,to,min(cf,e.capacity)))>0) {
				e.capacity -= tf;
				E[e.to][e.reve].capacity += tf;
				return tf;
			}
		}
		return 0;
	}
	
	int maxflow(int from, int to) {
		int fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,1<<29))==0) return fl;
			fl+=tf;
		}
	}
};


class BlockTheBlockPuzzle {
	public:
	int N,gx,gy;
	int minimumHoles(vector <string> board) {
		int y,x,s,t;
		N=board.size();
		queue<int> Q;
		FOR(y,N) FOR(x,N) if(board[y][x]=='$') gy=y,gx=x;
		
		MaxFlow mf;
		mf.init();
		FOR(y,N) FOR(x,N) {
			if(abs(y-gy)%3==0 && abs(x-gx)%3==0) {
				if(board[y][x]=='H') continue;
				if(board[y][x]=='$') mf.add_edge(100+y*50+x,1,2500);
				if(board[y][x]=='b') mf.add_edge(0,3000+y*50+x,2500);
				if(board[y][x]=='.') mf.add_edge(100+y*50+x,3000+y*50+x,1);
				if(x+3<N) {
					s=(board[y][x+1]=='.')+(board[y][x+2]=='.');
					if(board[y][x+1]=='b' || board[y][x+2]=='b') s=2500;
					if(s>0) {
						mf.add_edge(3000+y*50+x,100+y*50+(x+1),s);
						mf.add_edge(100+y*50+(x+1),100+y*50+x,s);
					}
				}
				if(x>=3) {
					s=(board[y][x-1]=='.')+(board[y][x-2]=='.');
					if(board[y][x-1]=='b' || board[y][x-2]=='b') s=2500;
					if(s>0) {
						mf.add_edge(3000+y*50+x,100+y*50+(x-2),s);
						mf.add_edge(100+y*50+(x-2),100+y*50+x,s);
					}
				}
				if(y+3<N) {
					s=(board[y+1][x]=='.')+(board[y+2][x]=='.');
					if(board[y+1][x]=='b' || board[y+2][x]=='b') s=2500;
					if(s>0) {
						mf.add_edge(3000+y*50+x,100+(y+1)*50+x,s);
						mf.add_edge(100+(y+1)*50+x,100+y*50+x,s);
					}
				}
				if(y>=3) {
					s=(board[y-1][x]=='.')+(board[y-2][x]=='.');
					if(board[y-1][x]=='b' || board[y-2][x]=='b') s=2500;
					if(s>0) {
						mf.add_edge(3000+y*50+x,100+(y-2)*50+x,s);
						mf.add_edge(100+(y-2)*50+x,100+y*50+x,s);
					}
				}
			}
			
		}
		x=mf.maxflow(0,1);
		if(x>=2500) return -1;
		return x;
	}
}

まとめ

面白い問題だったのに解けなかったのが惜しい。
最近最大カットを求める問題よく見るな。