AcWing 1107. 魔板
原题链接
简单
作者:
ACSaber
,
2021-06-13 21:47:22
,
所有人可见
,
阅读 297
import java.util.*;
class Main {
static int[] a = new int[10];
static int[] t = new int[10];
static Map<String, Integer> dist = new HashMap<>();
static Map<String, int[]> g = new HashMap<>();
static Map<String, Character> op = new HashMap<>();
static Deque<int[]> q = new ArrayDeque<>();
static int[][] tmp = new int[2][4];
static void set(int[] cur) {
for (int i = 0; i < 4; i++) tmp[0][i] = cur[i + 1];
for (int i = 0; i < 4; i++) tmp[1][i] = cur[8 - i];
}
static int[] get() {
int[] ans = new int[10];
for (int i = 0; i < 4; i++) ans[i + 1] = tmp[0][i];
for (int i = 0; i < 4; i++) ans[5 + i] = tmp[1][3 - i];
return ans;
}
static int[] move0(int[] cur) {
set(cur);
for (int i = 0; i < 4; i++) {
int c = tmp[0][i];
tmp[0][i] = tmp[1][i];
tmp[1][i] = c;
}
return get();
}
static int[] move1(int[] cur) {
set(cur);
int x = tmp[0][3], y = tmp[1][3];
for (int i = 3; i >= 1; i--) {
tmp[0][i] = tmp[0][i - 1];
tmp[1][i] = tmp[1][i - 1];
}
tmp[0][0] = x;
tmp[1][0] = y;
return get();
}
static int[] move2(int[] cur) {
set(cur);
int c = tmp[1][1];
tmp[1][1] = tmp[1][2];
tmp[1][2] = tmp[0][2];
tmp[0][2] = tmp[0][1];
tmp[0][1] = c;
return get();
}
static String getHash(int[] cur) {
StringBuilder sb = new StringBuilder();
for (int i : cur) {
sb.append(String.valueOf(i) + "_");
}
return sb.toString();
}
static void bfs() {
q.addLast(a);
dist.put(getHash(a), 0);
while (!q.isEmpty()) {
int[] poll = q.pollFirst();
// System.out.println(Arrays.toString(poll));
// System.out.println(q.size());
int di = dist.get(getHash(poll));
if (check(poll, t)) {
return;
}
List<int[]> list = new ArrayList<>();
list.add(move0(poll));
list.add(move1(poll));
list.add(move2(poll));
for (int i = 0; i < 3; i++) {
int[] cc = list.get(i);
String key = getHash(cc);
if (!dist.containsKey(key)) {
// System.out.println(key);
q.addLast(cc);
dist.put(key, di + 1);
op.put(key, (char)('A' + i));
g.put(key, poll);
if (check(cc, t)) return;
}
}
}
}
static boolean check(int[] a, int[] b) {
for (int i = 1 ; i <= 8; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int i = 1; i <= 8; i++) {
t[i] = sc.nextInt();
a[i] = i;
}
bfs();
System.out.println(dist.get(getHash(t)));
StringBuilder sb = new StringBuilder();
if (dist.get(getHash(t)) != 0) {
while (!check(t, a)) {
sb.append(op.get(getHash(t)));
t = g.get(getHash(t));
}
sb.reverse();
System.out.println(sb.toString());
}
}
}