题目链接

滑动谜题https://leetcode.cn/problems/sliding-puzzle/如果对BFS不太了解，可以浏览下方的文章，对BFS有一个大致的了解：

BFS（迷宫问题）https://blog.csdn.net/weixin_51882166/article/details/125891504

题目解析

题目：

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

某一块板子的初始状态：

我们需要考虑，每次可以进行的操作是什么？

 每一层都可能会进行相应的操作，这种情况下考虑BFS。

我们的目标是：

现在的问题是，如何把二维数字简化，使得我们处理起来更简单？

首先，我们要做的是把二维数组拉平：

拉平后，如何找到每次进行的选择？

  根据上图，下标4的位置，可以做的选择有三种（1，3，5），由于规模是固定的，每个位置可以做的选择也是可以手算观察得到。如果空白块在0号位置，它能做的选择就只有两种，向下或者向右，（1，3），依次类推，得到空白块在所有位置所能移动的可能性：

 //空白块在每个位置，所能移动的位置static int[][] move = {{1, 3},{0, 4, 2},{1, 5},{0, 4},{1, 3, 5},{4, 2}};

为了便于处理，把拉长后的序列变成字符串，每次只需交换字符串里两个字符的位置，生成新字符即可：

 //交换空白块和其他块的位置static String swap(String s, int i, int j) {char[] c = s.toCharArray();char t = c[i];c[i] = c[j];c[j] = t;return new String(c);}

对于层序遍历，使用队列来进行，完整代码如下：

import java.util.HashSet;
import java.util.Queue;class Solution {//空白块在每个位置，所能移动的位置static int[][] move = {{1, 3},{0, 4, 2},{1, 5},{0, 4},{1, 3, 5},{4, 2}};//交换空白块和其他块的位置static String swap(String s, int i, int j) {char[] c = s.toCharArray();char t = c[i];c[i] = c[j];c[j] = t;return new String(c);}public int slidingPuzzle(int[][] board) {int m = 2, n = 3;//目标String target = "123450";//起点StringBuffer buf = new StringBuffer();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {buf.append(board[i][j]);}}String start = buf.toString();int step = 0;Queue Q = new LinkedList();//set判重Set used = new HashSet<>();Q.add(start);used.add(start);while (!Q.isEmpty()) {int sz = Q.size();while (sz-- > 0) {String cur = Q.poll();if (cur.equals(target)) return step;//找到空格0的位置int idx = 0;while (cur.charAt(idx)!='0'){idx++;}//把空格所能走到的每一步加入队列，并且判重for (int next : move[idx]) {String nextS = swap(cur, idx, next);if (!used.contains(nextS)) {Q.add(nextS);used.add(nextS);}}}step++;}return -1;}
}

提交测试：