2010年 模擬地区予選 Problem D : Dice Room [Licence: NYSL Version 0.9982]

Main.java

import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {
  public static void main(String... args) {
		new Main().run();
	}

	static final int INF = 5;

	public void run() {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			boolean[][] dat = new boolean[6][];
			for (int i = 0; i < 6; i++) {
				char[][] map = new char[3][];
				for (int j = 0; j < 3; j++) {
					map[j] = sc.next().toCharArray();
					if(map[j][0] == '#')
						return;
				}
				dat[i] = check(map);
			}
			dat = new DiceBuilder().build(dat);

			Deque<DiceState> que = new ArrayDeque<DiceState>();
			que.offerLast(new DiceState());
			int[][] min = new int[6][4];
			for (int i = 0; i < 6; i++)
				for (int j = 0; j < 4; j++)
					min[i][j] = INF;
			min[0][0] = 0;
			while (!que.isEmpty()) {
				DiceState dice = que.pollFirst();
				if (isGoal(dice, dat)) {
					System.out.println(min[dice.cf][dice.cd]);
					break;
				}
				for (int d = 0; d < 4; d++) {
					DiceState nd = dice.roll(2).roll(d).roll(0);
					if (min[nd.cf][nd.cd] == INF) {
						min[nd.cf][nd.cd] = min[dice.cf][dice.cd] + 1;
						que.offerLast(nd);
					}
				}
			}
		}
	}

	boolean isGoal(DiceState d, boolean[][] dat) {
		DiceState t = d.roll(1).roll(1);
		return dat[d.cf][d.cd] && dat[t.cf][t.cd];
	}

	private boolean[] check(char[][] map) {
		boolean[] ret = new boolean[4];
		ret[0] = map[2][0] == '*' || map[2][1] == '*' || map[2][2] == '*';
		ret[1] = map[0][2] == '*' || map[1][2] == '*' || map[2][2] == '*';
		ret[2] = map[0][0] == '*' || map[0][1] == '*' || map[0][2] == '*';
		ret[3] = map[0][0] == '*' || map[1][0] == '*' || map[2][0] == '*';
		return ret;
	}

	public static class DiceState {
		private static final int[][] FM = { { 4, 5, 1, 2 }, { 4, 2, 1, 5 } };
		private static final int[][] DR = { { 1, 3, 3, 3 }, { 3, 1, 1, 1 } };
		// { 1, 2, 3, 6, 5, 4 } { U, L, D, R }
		public final int cf, cd;

		private DiceState(int cf, int cd) {
			this.cf = cf;
			this.cd = cd;
		}

		public DiceState() {
			this(0, 0);
		}

		public DiceState roll(int d) {
			int f = cf % 2;
			int c = (cd + d) % 4;
			return new DiceState((cf + FM[f][c]) % 6, (cd + DR[f][c]) % 4);
		}
	}

	public static class DiceBuilder {
		private final boolean[][] dat = new boolean[6][4];
		private final boolean[] visited = new boolean[6];
		private static final String[] map = { "4...", "0123", "5..." };
		private int si = 1, sj = 0;

		public boolean[][] build(boolean[][] in) {
			dfs(new DiceState(), si, sj, in);
			return dat;
		}

		void dfs(DiceState ds, int i, int j, boolean[][] in) {
			if (inRec(i, j) && map[i].charAt(j) != '.' && !visited[ds.cf]) {
				visited[ds.cf] = true;
				for (int d = 0; d < 4; d++)
					dat[ds.cf][(ds.cd + d) % 4] = in[map[i].charAt(j) - '0'][d];
				for (int d = 0; d < 4; d++)
					dfs(ds.roll(d), i + di[d], j + dj[d], in);
			}
		}

		private static final int[] di = { -1, 0, 1, 0 };
		private static final int[] dj = { 0, -1, 0, 1 };

		private static boolean inRec(int i, int j) {
			return i >= 0 && j >= 0 && i < map.length && j < map[0].length();
		}
	}
}