773. 滑动谜题（BFS）-蒲公英云

773. 滑动谜题（BFS）

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

773. 滑动谜题

题目
解题思路
代码

题目

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

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

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

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

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}
        };

在这里插入图片描述

在一维字符串中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);
    }
}