Google Code Jam Round3 問題Bの回答
えー、コチラで「B問題は処理に時間がかかる」とか「A*使うがいいよ」とか書いてますが、ウソでございます。ごめんなさい。
まず、A*は使いません。たぶん。自分のコードを見直してみたら、ヒューリスティックスが全然役に立ってなかった。ただのダイクストラでした。ダイクストラで解けます。
で、B問題は処理に時間がかかるという話も、正しい条件でコードを書けば一瞬でした。B-Largeはウチの環境で3秒で解けます。
ちょっと条件が悪いコードを書いちゃうと8分近くかかってしまうのですが、環境がよいとギリギリLargeの投稿時間内に解けてしまうようです。これは、問題設定があんまり良くないような気がする。
一応、解いたコードを以下に添付します。
計算時間が8分から3秒になったのは、Stateクラスのフィールドを減らしたことによります。最初はyellow portalとblue portalの両方の座標をStateに入れていたんですが、portalの座標は1つしか保持する必要がないんですね(壁に隣接していたらportalへワープできる、として扱う)。
package GCJ.round3; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.Date; import java.util.Formatter; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; import java.util.Scanner; import java.util.concurrent.Callable; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; public class ProblemB implements Callable<String> { public static void main(String[] args) throws Exception { BufferedReader rd = new BufferedReader(new InputStreamReader(System.in)); Scanner sc = new Scanner(rd); int n = Integer.parseInt(rd.readLine()); ExecutorService executor = Executors.newFixedThreadPool(2); boolean MT = true; Formatter fmt = new Formatter(); if (MT) { ArrayList<Future<String>> futures = new ArrayList<Future<String>>(); for (int i = 0; i < n; ++i) { futures.add(executor.submit(new ProblemB(sc))); } for (int i = 0; i < n; ++i) { fmt.format("Case #%d: %s\n", i + 1, futures.get(i).get()); } } else { for (int i = 0; i < n; ++i) { fmt.format("Case #%d: %s\n", i + 1, new ProblemB(sc).call()); } } System.out.println(fmt.toString()); BufferedWriter bw = null; try { String f = "/" + ProblemB.class.getName() + "_" + new Date().getTime() + ".txt"; bw = new BufferedWriter(new OutputStreamWriter( new FileOutputStream(f))); bw.write(fmt.toString()); } catch (Exception e) { } finally { bw.close(); } executor.shutdown(); System.exit(0); } int R, C; char[][] map; State startStat; int[] goal = new int[2]; static boolean b; public ProblemB(Scanner sc) throws IOException { R = sc.nextInt(); C = sc.nextInt(); sc.nextLine(); startStat = new State(); startStat.entrance[0] = startStat.entrance[1] = -1; map = new char[R + 2][]; for (int i = 1; i < R + 1; ++i) { String line = "#" + sc.nextLine() + "#"; assert line.length() == C + 2; if (line.indexOf('O') != -1) { startStat.pos[0] = i; startStat.pos[1] = line.indexOf('O'); } if (line.indexOf('X') != -1) { goal[0] = i; goal[1] = line.indexOf('X'); } map[i] = line.replaceAll("[OX]", ".").toCharArray(); } map[R + 1] = map[0] = new char[C + 2]; Arrays.fill(map[0], '#'); } Map<State, Integer> stat2cost = new HashMap<State, Integer>(); PriorityQueue<Pair> openlist; public String call() throws Exception { stat2cost.put(startStat, 0); openlist = new PriorityQueue<Pair>(10000, new PairComp()); Pair stp = new Pair(); stp.cost = 0; stp.stat = startStat; openlist.add(stp); Pair p; while (true) { p = openlist.poll(); if (p == null) { return "THE CAKE IS A LIE"; } State s = p.stat; if (State.eqa(goal, s.pos)) { break; } // System.out.println(s.toString() + ", " + p.cost); int[][] dir = { { -1, 0 }, { 0, -1 }, { +1, 0 }, { 0, +1 }, }; // shot for (int i = 0; i < 4; ++i) { int[] d = dir[i]; int[] tp = new int[2]; tp[0] = s.pos[0]; tp[1] = s.pos[1]; for (; map[tp[0]][tp[1]] == '.'; tp[0] += d[0], tp[1] += d[1]) ; State ts = new State(s); ts.entrance[0] = tp[0] - d[0]; ts.entrance[1] = tp[1] - d[1]; Integer cost = stat2cost.get(ts); int newcost = p.cost; if (cost != null && cost <= newcost) continue; stat2cost.put(ts, newcost); Pair newp = new Pair(); newp.stat = ts; newp.cost = newcost; openlist.offer(newp); } // move for (int[] d : dir) { State newss = new State(s); if (map[s.pos[0] + d[0]][s.pos[1] + d[1]] != '#') { newss.pos[0] += d[0]; newss.pos[1] += d[1]; } else if(s.entrance[0]!=-1){ newss.pos[0] = s.entrance[0]; newss.pos[1] = s.entrance[1]; } else { continue; } Integer cost = stat2cost.get(newss); int newcost = p.cost + 1; if (cost == null || cost > newcost) { stat2cost.put(newss, newcost); Pair newp = new Pair(); newp.stat = newss; newp.cost = newcost; openlist.offer(newp); } } } System.out.print("*"); return Integer.toString(p.cost); } } class State { int pos[]; int entrance[]; State() { pos = new int[2]; entrance = new int[2]; } State(State s) { pos = Arrays.copyOf(s.pos, 2); entrance = new int[2]; for (int i = 0; i < 2; ++i) { entrance[i] = s.entrance[i]; } } @Override public int hashCode() { return pos[0] ^ (pos[1] << 4) ^ (entrance[0] << 8) ^ (entrance[1] << 12); } @Override public boolean equals(Object obj) { State s = (State) obj; return eqa(pos, s.pos) && eqa(entrance, s.entrance); } static boolean eqa(int[] a, int[] b) { for (int i = 0; i < a.length; ++i) { if (a[i] != b[i]) { return false; } } return true; } @Override public String toString() { Formatter fmt = new Formatter(); fmt.format("pos=(%d, %d), p1=(%d, %d)", pos[0], pos[1], entrance[0], entrance[1]); return fmt.toString(); } } class Pair { State stat; int cost; } class PairComp implements Comparator<Pair> { PairComp() { } @Override public int compare(Pair l, Pair r) { return l.cost - r.cost; } }