如何用 BFS 算法秒杀各种智力题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：如何用 BFS 算法秒杀各种智力题

评论礼仪 见这里，违者直接拉黑。

[JackHo327]

这题看了解法有点类似 752. Open the Lock

[zhongweiLeex]

如752打开锁的那一题的双端回溯解法
需要注意：双端回溯需要在内部检查 q2 中是否存在 cur，意思就是从前往后 和从后往前碰到一起了，就是找到了，既需要返回step了，这个思路前文中提到过。

class Solution {
    public int slidingPuzzle(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                sb.append(board[i][j]);
            }
        }
        String start = sb.toString();
        String target = "123450";

        //0 在各个位置的相邻节点的索引
        int[][] neighbor = new int[][]{
            {1,3},
            {0,4,2},
            {1,5},
            {0,4},
            {3,1,5},
            {4,2}
        };

        Queue<String> q1 = new LinkedList<>();
        Queue<String> q2 = new LinkedList<>();
        //存储相同字符串是否被拜访过
        HashSet<String> visited = new HashSet<>();
        q1.offer(start);
        q2.offer(target);
        visited.add(start);

        int step = 0;
        while(!q1.isEmpty()&&!q2.isEmpty()){
            Queue<String> temp = new LinkedList<>();
            int size = q1.size();
            for(int i = 0; i<size;i++){
                String cur = q1.poll();
                
                if(q2.contains(cur)){
                    return step;
                }
                visited.add(cur);
                
                int index = 0;
                for(;cur.charAt(index)!='0';index++);//找到0的索引位置
                //0 和 其相邻的数字交换位置
                for(int adj : neighbor[index]){
                    String new_board = swap(cur.toCharArray(),adj,index);
                    if(!visited.contains(new_board)){
                        temp.offer(new_board);
                    }
                }
            }
            step++;
            q1 = q2;
            q2 = temp;
        }
        return -1;
    }
    private String swap(char[] chars,int i , int j ){
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        return new String(chars);
    }
}

[bert82503]

打卡，感谢楼主！

[MarlonDML]

比楼主写的复杂点，但是应该更清晰直观吧？

class Solution {

    public int slidingPuzzle(int[][] board) {

        LinkedList<String> pass = new LinkedList<>();

        //记录个可能的字符串，以及对应 0 的位置
        HashMap<String, Integer> visited = new HashMap<>();

        StringBuilder sb = new StringBuilder();

        //记录 0 在 一维字符串中的位置
        int index = 0;

        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(board[i][j] == 0) {
                    //初始位置
                    index = i * 3 + j;
                }
                sb.append(board[i][j]);
            }
        }
        String str = sb.toString();

        pass.add(str);
        visited.put(str, index);

        String target = "123450";

        //步数
        int step = 0;

        int size;

        //中间变量
        char[] chars;
        String s;
        int idx;

        while(!pass.isEmpty()) {
            size = pass.size();

            for(int i = 0; i < size; i++) {
                str = pass.poll();

                //最小步数
                if(str.equals(target)) {
                    return step;
                }

                //当前字符串中 0 的位置
                index = visited.get(str);

                chars = str.toCharArray();

                //向上移动，返回移动之后 0 的位置
                idx = up(chars, index);

                //移动成功，才进行后续操作
                if(idx != index) {
                    s = new String(chars);
                    if(!visited.containsKey(s)) {
                        pass.add(s);
                        visited.put(s, idx);
                    }
                }

                chars = str.toCharArray();

                //向下移动，返回移动之后 0 的位置
                idx = down(chars, index);
                if(idx != index) {
                    s = new String(chars);
                    if(!visited.containsKey(s)) {
                        pass.add(s);
                        visited.put(s, idx);
                    }
                }


                chars = str.toCharArray();
                //向左移动，返回移动之后 0 的位置
                idx = left(chars, index);
                if(idx != index) {
                    s = new String(chars);
                    if(!visited.containsKey(s)) {
                        pass.add(s);
                        visited.put(s, idx);
                    }
                }


                chars = str.toCharArray();
                //向右移动，返回移动之后 0 的位置
                idx = right(chars, index);
                if(idx != index) {
                    s = new String(chars);
                    if(!visited.containsKey(s)) {
                        pass.add(s);
                        visited.put(s, idx);
                    }
                }
            }
            //增加步数
            step++;
        }

        return -1;
    }

    //上
    public int up(char[] strs, int index) {

        if(index < 3) {
            return index;
        }
        char c = strs[index - 3];
        strs[index - 3] = strs[index];
        strs[index] = c;
        return index - 3;
    }

    //下
    public int down(char[] strs, int index) {

        if(index > 2) {
            return index;
        }
        char c = strs[index + 3];
        strs[index + 3] = strs[index];
        strs[index] = c;
        return index + 3;
    }

    //左
    public int left(char[] strs, int index) {

        if(index == 0 || index == 3) {
            return index;
        }
        char c = strs[index - 1];
        strs[index - 1] = strs[index];
        strs[index] = c;
        return index - 1;
    }

    //右
    public int right(char[] strs, int index) {

        if(index == 2 || index == 5) {
            return index;
        }
        char c = strs[index + 1];
        strs[index + 1] = strs[index];
        strs[index] = c;
        return index + 1;
    }
}

[chenxiiang]

港真，你这个真的不如楼主的，连看下去的勇气都没有了

[GoingMyWay]

有点长了。尽量缩短一些。

[bert82503]

@MarlonDML 朋友，你的实现代码的维护性如何？我有点审美疲劳，感觉你把简单事情复杂化了。

[muenzhang]

有点意思

[LebronHarden1]

牛皮牛皮,会不会有让你记录这个最短操作次数具体怎么操作的这种题

[labuladong]

@LebronHarden1 这也很好解决，自己包一个 Node 类记录具体操作，然后在队列里用 Node 做 BFS 算法。

[LebronHarden1]

@labuladong 恍然大悟

[doerme]

typescript跑不动.. OOM了

[freeduser]

我想问下，“邻居”数组里的元素顺序应该不重要，为啥我的顺序不对，导致结果不对呢？
{1,3},
{0,4,2},
{2,5},
{4,0},
{3,5,1},
{4,2}
这样不行

[ghost]

@freeduser 你第三个数组错了，是{1, 5} 不是{2, 5}

[dadasdsads]

请问楼主 为啥要把2维数组压缩为一维数组啊

[forexgg]

关键是：不是压缩成了一维数组，而是一个string。这样才能用set。

[Youareblind]

ruby版

# @param {Integer[][]} board
# @return {Integer}
def sliding_puzzle(board)
    require 'set'

    neighbour = [[1,3],[0,4,2],[1,5],[0,4],[3,1,5],[4,2]]
    start = board.flatten.join
    target = "123450"
    
    queue = []
    visited = Set.new

    queue.push start
    visited.add start

    step = 0
    until queue.empty? do
        sz = queue.size
        sz.times do
            cur = queue.shift
            return step if cur == target

            idx = cur.index '0'
            neighbour[idx].each do |nb|
                new_board = swap cur, nb, idx
                unless visited.include? new_board
                    queue.push new_board
                    visited.add new_board
                end
            end
        end
        step += 1  
    end
    -1
end

def swap board, i, j
    board_copy = board.dup
    board_copy[i], board_copy[j] = board_copy[j], board_copy[i]
    board_copy
end

[StephenLinux]

2X3的数组还是比较小的，直接用数组交换数据，python实现：

[StephenLinux]

import collections
import copy


class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        visited = set()
        target = [[1, 2, 3], [4, 5, 0]]
        queue = collections.deque()
        queue.append((board, 0))

        while queue:
            current_board, steps = queue.popleft()
            current_board_str = self._list_to_string(current_board)
            if current_board_str == self._list_to_string(target):
                return steps
            zero_x, zero_y = self._find_zero_index(current_board)
            for mx, my in [(zero_x, zero_y - 1), (zero_x, zero_y + 1), (zero_x + 1, zero_y), (zero_x - 1, zero_y)]:
                tmp_board = copy.deepcopy(current_board)
                if 0 <= mx < len(board) and 0 <= my < len(board[0]):
                    tmp_board[zero_x][zero_y], tmp_board[mx][my] = tmp_board[mx][my], \
                                                                   tmp_board[zero_x][zero_y]
                    board_string = self._list_to_string(tmp_board)
                    if board_string not in visited:
                        queue.append((tmp_board, steps + 1))
                        visited.add(board_string)
        return -1

    @staticmethod
    def _find_zero_index(board: List[List[int]]):
        for x_index in range(len(board)):
            for y_index in range(len(board[0])):
                if board[x_index][y_index] == 0:
                    return x_index, y_index

    @staticmethod
    def _list_to_string(board: List[List[int]]):
        return "".join([str(board[x][y]) for x in range(len(board)) for y in range(len(board[0]))])

[gnftau]

想请教一下，将二维数组展平成一维数组是不是方便在后面 BFS 中更快地与 target 做对比，更快比较两者是否相等？

[forexgg]

这是必须的。
因为list本身是，mutable的，所以加入不到set中。
Convert the board into a string format (or any other hashable format) for easy comparison and storage in data structures.

[Peter88645]

厉害， 写完之后 居然打败了 100% 的python 解法

[tingtingwang217]

请问这个解法的时间和空间复杂度分别是多少呀？

[forexgg]

用两维实现的代码。没有转换2D to 1D

from typing import List
from collections import deque


class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        target = [[1, 2, 3], [4, 5, 0]]
        m, n = len(board), len(board[0])
        zero_pos = self.findZero(board, m, n)
        q = deque([(board, zero_pos)])
        visited = {str(board)}
        moves = 0
        dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]  # left, right, up, down

        while q:
            for i in range(len(q)):
                board, zero_pos = q.popleft()

                if board == target:
                    return moves

                for dir in dirs:
                    i, j = zero_pos[0], zero_pos[1]
                    new_i, new_j = i + dir[0], j + dir[1]
                    new_zero_pos = (new_i, new_j)
                    if 0 <= new_i < m and 0 <= new_j < n:
                        new_board = [row[:] for row in board]
                        new_board[i][j], new_board[new_i][new_j] = new_board[new_i][new_j], new_board[i][j]
                        if str(new_board) not in visited:
                            q.append((new_board, new_zero_pos))
                            visited.add(str(new_board))
            moves += 1
        return -1

    def findZero(self, board, m, n):
        for i in range(m):
            for j in range(n):
                if board[i][j] == 0:
                    return (i, j)


board = [[4, 1, 2], [5, 0, 3]]
print('minMoves :', Solution().slidingPuzzle(board))

[shiboys]

确实秒