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;
	}
}