Skip to content

Instantly share code, notes, and snippets.

@hiroshi-cl
Created June 25, 2013 07:51
Show Gist options
  • Save hiroshi-cl/5856731 to your computer and use it in GitHub Desktop.
Save hiroshi-cl/5856731 to your computer and use it in GitHub Desktop.
2010年 模擬地区予選 Problem D : Dice Room [Licence: NYSL Version 0.9982]
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();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment