LeetCode

• 1.题目
• 2.思路
• 3.代码实现（Java）

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

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

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

示例 1：

输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5，1 步完成

示例 2：

输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板

示例 3：

输入：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.length == 2
board[i].length == 3
0 <= board[i][j] <= 5
board[i][j] 中每个值都 不同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sliding-puzzle

（1）BFS
思路参考如何用 BFS 算法秒杀各种智力题。

//思路1————BFS
class Solution {
    public int slidingPuzzle(int[][] board) {
        int m = 2;
        int n = 3;
        StringBuilder sBuilder = new StringBuilder();
        //将 2x3 的数组转换为字符串，然后将其作为 BFS 的起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sBuilder.append(board[i][j]);
            }
        }
        //可将数组内数字交换结束后对应的字符串"123450"看作终点
        String target = "123450";
        String start = sBuilder.toString();
        
        int[][] neighbor = new int[][] {
            {1, 3},         //board[0][0]
            {0, 4, 2},      //board[0][1]
            {1, 5},         //board[0][2]
            {0, 4},         //board[1][0]
            {3, 1, 5},      //board[1][1]
            {4, 2}          //board[1][2]
        };
        
        Queue queue = new LinkedList<>();
        //记录已经交换数字后得到的字符串，防止在遍历时走回头路
        HashSet visited = new HashSet<>();
        //记录最少移动解开谜板的次数，初始值为 0
        int minCnt = 0;
        //从起点开始 BFS
        queue.offer(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                //如果到达终点，则直接返回 minCnt 即可
                if (target.equals(cur)) {
                    return minCnt;
                }
                //找到数字 0 的索引
                int index = 0;
                while (cur.charAt(index) != '0') {
                    index++;
                }
                //将数字 0 和相邻的数字进行交换，即模拟移动的过程
                for (int adj : neighbor[index]) {
                    String newBoard = swap(cur.toCharArray(), adj, index);
                    //防止走回头路
                    if (!visited.contains(newBoard)) {
                        queue.offer(newBoard);
                        visited.add(newBoard);
                    }
                }
            }
            minCnt++;
        }
        //不能解开谜板，则返回 -1
        return -1;
    }

    //将字符数组 chs 中下标为 i 和 j 的字符进行交换，并将 chs 转换为字符串进行返回
    public String swap(char[] chs, int i, int j) {
        char tmp = chs[i];
        chs[i] = chs[j];
        chs[j] = tmp;
        return new String(chs);
    }
}