2012-03-26SRM360, SRM361 (Practice)
SRM 360 PrinceOfPersia
http://www.topcoder.com/stat?c=problem_statement&pm=7876
- 最大流っぽい
- 蟻本を見ながらグラフ構築。
- この問題は「頂点に流量の制約がある場合」に相当する。
- 出した。
- WA。あれ?
- グラフの作り方が違ってた・・・あとノード最大数は100じゃ足りない。
- 修正したら通った。
- ちなみに、Pの周りを#で囲めば必ず到達不可になるので、必要なブロックの数は高々4。
- このことから、ブロックの置き方をすべて試すBruteForce解もあるんじゃないかと思う
- 100C1 + 100C2 + 100C3 + 100C4 = 4M+α ぐらい。
- 未検証
- このことから、ブロックの置き方をすべて試すBruteForce解もあるんじゃないかと思う
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); } }
コメント