hama_DU@TopCoderへの道

SRM 360 PrinceOfPersia

Java, div1q2 |

http://www.topcoder.com/stat?c=problem_statement&pm=7876

• 最大流っぽい
  • 蟻本を見ながらグラフ構築。
  • この問題は「頂点に流量の制約がある場合」に相当する。
• 出した。
  • WA。あれ？
  • グラフの作り方が違ってた・・・あとノード最大数は100じゃ足りない。
• 修正したら通った。

• ちなみに、Pの周りを#で囲めば必ず到達不可になるので、必要なブロックの数は高々4。
  • このことから、ブロックの置き方をすべて試すBruteForce解もあるんじゃないかと思う
    • 100C1 + 100C2 + 100C3 + 100C4 = 4M+α ぐらい。
    • 未検証

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class PrinceOfPersia {

	int[] dx = {1, 0, -1, 0};
	int[] dy = {0, 1, 0, -1};
	
	public class Edge {
		int to;
		int cap;
		int rev;
		public Edge(int _to, int _cap, int _rev) {
			to = _to;
			cap = _cap;
			rev = _rev;
		}
	}
	public Map<Integer, List<Edge>> graph = new HashMap<Integer, List<Edge>>();
	public boolean[] used;
	public void init(int size) {
		for (int i = 0 ; i < size ; i++) {
			graph.put(i, new ArrayList<Edge>());
		}
		used = new boolean[size];
	}
	public void edge(int from, int to, int cap) {
		graph.get(from).add(new Edge(to, cap, graph.get(to).size()));
		graph.get(to).add(new Edge(from, 0, graph.get(from).size() - 1));
	}
	public int dfs(int v, int t, int f) {
		if (v == t) return f;
		used[v] = true;
		for (int i = 0 ; i < graph.get(v).size() ; i++) {
			Edge e = graph.get(v).get(i);
			if (!used[e.to] && e.cap > 0) {
				int d = dfs(e.to, t, Math.min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					graph.get(e.to).get(e.rev).cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	public int max_flow(int s, int t) {
		int flow = 0;
		while (true) {
			used = new boolean[graph.size()];
			int f = dfs(s, t, Integer.MAX_VALUE);
			if (f == 0) {
				break;
			}
			flow += f;
		}
		return flow;
	}
	
	public int minObstacles(String[] maze) {
		int h = maze.length;
		int w = maze[0].length();
		
		// 最大流
		boolean[][] done = new boolean[200][200];
		int nodes = h * w;
		init(500);
		
		int sx = 0, sy = -1;
		int gx = 0, gy = -1;
		int fromid = 0;
		int toid = 0;
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				if (maze[i].charAt(j) == 'P') {
					if (sy == -1) {
						sx = j;
						sy = i;
						fromid = i*w+j;
					} else {
						gx = j;
						gy = i;
						toid = i*w+j;
					}
				}
				if (maze[i].charAt(j) != '#') {
					int id1 = i*w+j;
					edge(id1, id1+200, 1);
				}
				
				for (int d = 0 ; d < 4 ; d++) {
					int tx = j+dx[d];
					int ty = i+dy[d];
					if (tx < 0 || tx >= w || ty < 0 || ty >= h) {
						continue;
					}
					if (maze[i].charAt(j) != '#' && maze[ty].charAt(tx) != '#') {
						int id1 = i*w+j;
						int id2 = ty*w+tx;
						edge(id1+200, id2, 100);
						edge(id2+200, id1, 100);
					}
				}
			}
		}
		
		// 直接行けるかチェック
		int dd = Math.abs(sx - gx) + Math.abs(sy - gy);
		if (dd == 1) {
			return -1;
		}	
		return max_flow(fromid+200, toid);
	}
}