05 August 2008
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
为了方便，将原来的二维矩阵转成字符串（一维矩阵）进行处理。
这样带来的好处直接可以作为哈希 Key 使用，也可以很方便进行「二维坐标」与「一维下标」的转换。
由于固定是 2∗3 的格子，因此任意的合法二维坐标 (x,y) 和对应一维下标 idx 可通过以下转换：
idx = x ∗ 3 + y
x = idx / 3, y = idx
其余的就是常规的 BFS 过程了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
class Node {
String str;
int x, y;
Node(String _str, int _x, int _y) {
str = _str;
x = _x;
y = _y;
}
}
int n = 2, m = 3;
String s, e;
int x, y;
public int slidingPuzzle(int[][] board) {
s = "";
e = "123450";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
s += board[i][j];
if (board[i][j] == 0) {
x = i;
y = j;
}
}
}
int result = bfs();
return result;
}
int[][] dirs = new int[][]{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int bfs() {
Deque<Node> deque = new ArrayDeque<>();
Map<String, Integer> map = new HashMap<>();
Node root = new Node(s, x, y);
deque.addLast(root);
map.put(s, 0);
while (!deque.isEmpty()) {
Node poll = deque.pollFirst();
int step = map.get(poll.str);
if (poll.str.equals(e)) return step;
int dx = poll.x, dy = poll.y;
for (int[] di : dirs) {
int nx = dx + di[0], ny = dy + di[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
String nStr = update(poll.str, dx, dy, nx, ny);
if (map.containsKey(nStr)) continue;
Node next = new Node(nStr, nx, ny);
deque.addLast(next);
map.put(nStr, step + 1);
}
}
return -1;
}
String update(String cur, int i, int j, int p, int q) {
char[] cs = cur.toCharArray();
char tmp = cs[i * m + j];
cs[i * m + j] = cs[p * m + q];
cs[p * m + q] = tmp;
return String.valueOf(cs);
}
}
可以直接根据本题规则来设计 A* 的「启发式函数」。
比如对于两个状态 a 和 b 可直接计算出「理论最小转换次数」：所有位置的数值「所在位置」与「目标位置」的曼哈顿距离之和（即横纵坐标绝对值之和） 。
注意，我们只需要计算「非空格」位置的曼哈顿距离即可，因为空格的位置会由其余数字占掉哪些位置而唯一确定。
A* 求最短路的正确性问题：由于我们衡量某个状态 str 的估值是以目标字符串 e=123450 为基准，因此我们只能确保 e 出队时为「距离最短」，而不能确保中间节点出队时「距离最短」，因此我们不能单纯根据某个节点是否「曾经入队」而决定是否入队，还要结合当前节点的「最小距离」是否被更新而决定是否入队。
这一点十分关键，在代码层面上体现在 map.get(nStr) > step + 1 的判断上。
我们知道，A* 在有解的情况下，才会发挥「启发式搜索」的最大价值，因此如果我们能够提前判断无解的情况，对 A* 算法来说会是巨大的提升。
而对于通用的 N * N 数码问题，判定有解的一个充要条件是：「逆序对」数量为偶数，如果不满足，必然无解，直接返回 −1 即可。
对该结论的充分性证明和必要性证明完全不在一个难度上，所以建议记住这个结论即可。
但本题是 2 * 32∗3 的数码问题，结论是否还成立呢？
答案是成立的，对于任意的 N * M 的数码问题，只要确保 M 为奇数，逆序对数量为偶数，必然有解（因为此时四联通的操作不会改变奇偶性）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class Solution {
class Node {
String str;
int x, y;
int val;
Node(String _str, int _x, int _y, int _val) {
str = _str;
x = _x;
y = _y;
val = _val;
}
}
int f(String str) {
int ans = 0;
char[] cs1 = str.toCharArray(), cs2 = e.toCharArray();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 跳过「空格」，计算其余数值的曼哈顿距离
if (cs1[i * m + j] == '0' || cs2[i * m + j] == '0') continue;
int cur = cs1[i * m + j], next = cs2[i * m + j];
int xd = Math.abs((cur - 1) / 3 - (next - 1) / 3);
int yd = Math.abs((cur - 1) % 3 - (next - 1) % 3);
ans += (xd + yd);
}
}
return ans;
}
int n = 2, m = 3;
String s, e;
int x, y;
public int slidingPuzzle(int[][] board) {
s = "";
e = "123450";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
s += board[i][j];
if (board[i][j] == 0) {
x = i;
y = j;
}
}
}
// 提前判断无解情况
if (!check(s)) return -1;
int[][] dirs = new int[][]{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
Node root = new Node(s, x, y, f(s));
PriorityQueue<Node> q = new PriorityQueue<>((a, b) -> a.val - b.val);
Map<String, Integer> map = new HashMap<>();
q.add(root);
map.put(s, 0);
while (!q.isEmpty()) {
Node poll = q.poll();
int step = map.get(poll.str);
if (poll.str.equals(e)) return step;
int dx = poll.x, dy = poll.y;
for (int[] di : dirs) {
int nx = dx + di[0], ny = dy + di[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
String nStr = update(poll.str, dx, dy, nx, ny);
if (!map.containsKey(nStr) || map.get(nStr) > step + 1) {
Node next = new Node(nStr, nx, ny, step + 1 + f(nStr));
q.add(next);
map.put(nStr, step + 1);
}
}
}
return 0x3f3f3f3f; // never
}
String update(String cur, int i, int j, int p, int q) {
char[] cs = cur.toCharArray();
char tmp = cs[i * m + j];
cs[i * m + j] = cs[p * m + q];
cs[p * m + q] = tmp;
return String.valueOf(cs);
}
boolean check(String str) {
char[] cs = str.toCharArray();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n * m; i++) {
if (cs[i] != '0') list.add(cs[i] - '0');
}
int cnt = 0;
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
if (list.get(i) > list.get(j)) cnt++;
}
}
return cnt % 2 == 0;
}
}