773. 滑动谜题（BFS）

向右看齐 2023-10-05 19:52 9阅读 0赞

#### 773. 滑动谜题 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.

一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.

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

给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]  
**提示：**

*  board 是一个如上所述的 2 x 3 的数组.
 *  board\[i\]\[j\] 是一个 \[0, 1, 2, 3, 4, 5\] 的排列.

## 解题思路 ##

对于这种计算最小步数的问题，我们就要敏感地想到 BFS 算法。

每次先找到数字 0，然后和周围的数字进行交换，形成新的局面加入队列…… 当第一次到达 target 时，就得到了赢得游戏的最少步数。

这里的 board 仅仅是 2x3 的二维数组，所以可以压缩成一个一维字符串。其中比较有技巧性的点在于，二维数组有「上下左右」的概念，压缩成一维后，如何得到某一个索引上下左右的索引？

很简单，我们只要手动写出来这个映射就行了：

int[][] neighbor = new int[][]{
        
                    {
        1, 3},
                    {
        0, 4, 2},
                    {
        1, 5},
                    {
        0, 4},
                    {
        3, 1, 5},
                    {
        4, 2}
            };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]

> 在一维字符串中`0`的下标为4，那么`0`在原来二维数组的相邻元素是`4、5、3`它们对应的索引是：`1、3、5`。也就是`neighbor[4]`。

至此，我们就把这个问题完全转化成标准的 BFS 问题了。接下来就只要套模板了。

## 代码 ##

class Solution {
        
        public int slidingPuzzle(int[][] board) {
        
            int m = 2;
            int n = 3;
            String start = "";
            StringBuffer sb = new StringBuffer();
            String target = "123450";
            //将2*3的数组转化成一个字符串
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    sb.append(board[i][j]);
                    start = sb.toString();
                }
            }
    
            //记录在一维字符串中 某个元素在 原来二维数组 中的 相邻元素 的索引。
            int[][] neighbor = new int[][]{
        
                    {
        1, 3},
                    {
        0, 4, 2},
                    {
        1, 5},
                    {
        0, 4},
                    {
        3, 1, 5},
                    {
        4, 2}
            };
    
            /*开始BFS*/
            Queue<String> q = new LinkedList<>();
            Set<String> visited = new HashSet<>();
    
    
            q.offer(start);
            visited.add(start);
            int step = 0;//因为start就是初始值，没有动过，所以步数不需要从1开始
    
            while (!q.isEmpty()) {
        
                int size = q.size();
                for (int i = 0; i < size; i++) {
        
                    String cur = q.poll();
    
                    if (cur.equals(target)) {
        
                        return step;
                    }
    
                    //idx用来保存‘0’的索引。因为我们只可以移动‘0’
                    int idx = 0;
                    //这个循环就是从字符串中找到‘0’的索引
                    for (; cur.charAt(idx) != '0'; idx++) {
        
                    }
    
                    //交换0和相邻元素的位置
    //                neighbor[idx]：和0在二维数组中相邻元素的索引
                    for (int adj : neighbor[idx]) {
        
                        String new_board = cur;
                        new_board = exchangeString(new_board, idx, adj);
    
                        if (!visited.contains(new_board)) {
        
                            q.offer(new_board);
                            visited.add(new_board);
                        }
                    }
                }
                step++;
            }
    
            return -1;
        }
    
    
        /**
         * 交换字符
         *
         * @param string
         * @param src
         * @param dis
         * @return
         */
        public String exchangeString(String string, int src, int dis) {
        
            char[] chars = string.toCharArray();
            char temp = chars[dis];
            chars[dis] = chars[src];
            chars[src] = temp;
            return new String(chars);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210218142923501.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2021021814310197.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70