LeetCode_BFS_困难_773. 滑动谜题

迈不过友情╰ 2023-10-06 22:42 25阅读 0赞

#### 目录 ####

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

## 1.题目 ##

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

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

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

**示例 1：**  
![在这里插入图片描述][d0836c4fcc264181a864337762268f5b.png]  
输入：board = \[\[1,2,3\],\[4,0,5\]\]  
输出：1  
解释：交换 0 和 5，1 步完成

**示例 2：**  
![在这里插入图片描述][12b573f9cab54f97947e99588882e9d2.png]  
输入：board = \[\[1,2,3\],\[5,4,0\]\]  
输出：-1  
解释：没有办法完成谜板

**示例 3：**  
![在这里插入图片描述][f41bc1815c904ce8bfddef4131baa1a5.png]  
输入：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

## 2.思路 ##

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

## 3.代码实现（Java） ##

//思路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();
            /*
                记录一维字符串的相邻索引
                例如 start = "123405"，在原数组中与数字 1 相邻的数字有 2 和 4，
                那么它们在字符串 start 中的索引为{1, 3}，即 neighbor[0] = {1, 3}
            */
            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]
            };
            /*****BFS算法框架*****/
            Queue<String> queue = new LinkedList<>();
            //记录已经交换数字后得到的字符串，防止在遍历时走回头路
            HashSet<String> 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);
        }
    }

[d0836c4fcc264181a864337762268f5b.png]: https://img-blog.csdnimg.cn/d0836c4fcc264181a864337762268f5b.png
[12b573f9cab54f97947e99588882e9d2.png]: https://img-blog.csdnimg.cn/12b573f9cab54f97947e99588882e9d2.png
[f41bc1815c904ce8bfddef4131baa1a5.png]: https://img-blog.csdnimg.cn/f41bc1815c904ce8bfddef4131baa1a5.png
[BFS]: https://labuladong.github.io/algo/4/29/111/