题目描述
这是 LeetCode 上的 773. 滑动谜题 ，难度为 困难。
Tag : 「BFS」、「最小步数」、「AStar 算法」、「启发式搜索」
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
示例：
输入：board = [[1,2,3],[4,0,5]] 输出：1 解释：交换 0 和 5 ，1 步完成 复制代码
输入：board = [[1,2,3],[5,4,0]] 输出：-1 解释：没有办法完成谜板 复制代码
输入：board = [[4,1,2],[5,0,3]] 输出：5 解释： 最少完成谜板的最少移动次数是 5 ， 一种移动路径: 尚未移动: [[4,1,2],[5,0,3]] 移动 1 次: [[4,1,2],[0,5,3]] 移动 2 次: [[0,1,2],[4,5,3]] 移动 3 次: [[1,0,2],[4,5,3]] 移动 4 次: [[1,2,0],[4,5,3]] 移动 5 次: [[1,2,3],[4,5,0]] 复制代码
输入：board = [[3,2,4],[1,5,0]] 输出：14 复制代码
提示：
- board 是一个如上所述的 2 x 3 的数组.
- board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.
基本分析
这是八数码问题的简化版：将 3 * 33∗3 变为 2 * 32∗3，同时将「输出路径」变为「求最小步数」。
通常此类问题可以使用「BFS」、「AStar 算法」、「康拓展开」进行求解。
由于问题简化到了 2 * 32∗3，我们使用前两种解法即可。
BFS
为了方便，将原来的二维矩阵转成字符串（一维矩阵）进行处理。
这样带来的好处直接可以作为哈希 Key 使用，也可以很方便进行「二维坐标」与「一维下标」的转换。
由于固定是 2 * 32∗3 的格子，因此任意的合法二维坐标 (x, y)(x,y) 和对应一维下标 idxidx 可通过以下转换：
- idx = x * 3 + yidx=x∗3+y
- x = idx / 3,y = idx \% 3x=idx/3,y=idx%3
其余的就是常规的 BFS 过程了。
代码：
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 ans = bfs(); return ans; } int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}}; int bfs() { Deque<Node> d = new ArrayDeque<>(); Map<String, Integer> map = new HashMap<>(); Node root = new Node(s, x, y); d.addLast(root); map.put(s, 0); while (!d.isEmpty()) { Node poll = d.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); d.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* 的「启发式函数」。
比如对于两个状态 a 和 b 可直接计算出「理论最小转换次数」：所有位置的数值「所在位置」与「目标位置」的曼哈顿距离之和（即横纵坐标绝对值之和） 。
注意，我们只需要计算「非空格」位置的曼哈顿距离即可，因为空格的位置会由其余数字占掉哪些位置而唯一确定。
A* 求最短路的正确性问题：由于我们衡量某个状态 str 的估值是以目标字符串 e=123450 为基准，因此我们只能确保 e 出队时为「距离最短」，而不能确保中间节点出队时「距离最短」，因此我们不能单纯根据某个节点是否「曾经入队」而决定是否入队，还要结合当前节点的「最小距离」是否被更新而决定是否入队。
这一点十分关键，在代码层面上体现在 map.get(nStr) > step + 1 的判断上。
我们知道，A* 在有解的情况下，才会发挥「启发式搜索」的最大价值，因此如果我们能够提前判断无解的情况，对 A* 算法来说会是巨大的提升。
而对于通用的 N * NN∗N 数码问题，判定有解的一个充要条件是：「逆序对」数量为偶数，如果不满足，必然无解，直接返回 -1−1 即可。
对该结论的充分性证明和必要性证明完全不在一个难度上，所以建议记住这个结论即可。
代码：
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; } } 复制代码
最后
这是我们「刷穿 LeetCode」系列文章的第 No.773 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
