Leetcode 1263:推箱子(超详细的解法!!!)

(110) 2024-04-30 07:01:01

「推箱子」是一款风靡全球的益智小游戏,玩家需要将箱子推到仓库中的目标位置。

游戏地图用大小为 n * m 的网格 grid 表示,其中每个元素可以是墙、地板或者是箱子。

现在你将作为玩家参与游戏,按规则将箱子 'B' 移动到目标位置 'T'

  • 玩家用字符 'S' 表示,只要他在地板上,就可以在网格中向上、下、左、右四个方向移动。
  • 地板用字符 '.' 表示,意味着可以自由行走。
  • 墙用字符 '#' 表示,意味着障碍物,不能通行。
  • 箱子仅有一个,用字符 'B' 表示。相应地,网格上有一个目标位置 'T'
  • 玩家需要站在箱子旁边,然后沿着箱子的方向进行移动,此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
  • 玩家无法越过箱子。

返回将箱子推到目标位置的最小 推动 次数,如果无法做到,请返回 -1

示例 1:


Leetcode 1263:推箱子(超详细的解法!!!) (https://mushiming.com/)  第1张

输入:grid = [["#","#","#","#","#","#"],
             ["#","T","#","#","#","#"],
             ["#",".",".","B",".","#"],
             ["#",".","#","#",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出:3
解释:我们只需要返回推箱子的次数。

示例 2:

输入:grid = [["#","#","#","#","#","#"],
             ["#","T","#","#","#","#"],
             ["#",".",".","B",".","#"],
             ["#","#","#","#",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出:-1

示例 3:

输入:grid = [["#","#","#","#","#","#"],
             ["#","T",".",".","#","#"],
             ["#",".","#","B",".","#"],
             ["#",".",".",".",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出:5
解释:向下、向左、向左、向上再向上。

示例 4:

输入:grid = [["#","#","#","#","#","#","#"],
             ["#","S","#",".","B","T","#"],
             ["#","#","#","#","#","#","#"]]
输出:-1

提示:

  • 1 <= grid.length <= 20
  • 1 <= grid[i].length <= 20
  • grid 仅包含字符 '.', '#', 'S' , 'T', 以及 'B'
  • grid'S', 'B''T' 各只能出现一个。

解题思路

这个问题思路非常简单,代码比较复杂。我们需要判断箱子的最小推动次数,显然通过bfs来处理。

在推箱子的过程中,包括人的移动和箱子的移动两个部分,所以需要判断箱子是否可达(由于是最短路问题,所以这里通过bfs),并且判断人是不是可以到达箱子的后面去推它(通过bfsdfs处理,这里使用bfs)。在判断箱子是否可达的时候,bfs的队列中应该存储的箱子坐标和人的坐标两个状态,因为必须同时满足两个条件(人可达和箱子可达),那么箱子才算可达的。

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        r, c = len(grid), len(grid[0])
        dire = [[0, 1], [0, -1], [-1, 0], [1, 0]]
        for i in range(r):
            for j in range(c):
                if grid[i][j] == 'T':
                    T = (i, j)
                elif grid[i][j] == 'B':
                    B = (i, j)
                elif grid[i][j] == 'S':
                    S = (i, j)

        def check1(x, y):
            return x >= 0 and x < r and y >= 0 and y < c and grid[x][y] != '#'

        def canMoveTo(e, b, q, vis):
            while q:
                pre = q.pop(0)
                if pre == e:
                    return True

                for i, j in dire:
                    nx, ny = pre[0] + i, pre[1] + j
                    if check1(nx, ny) and \
                        (nx, ny) != b and (nx, ny) not in vis:
                        q.append((nx, ny))
                        vis.add((nx, ny))
            return False

        def move(e, q, vis):
            res = 0
            while q:
                for _ in range(len(q)):
                    b, p = q.pop(0)
                    if b == e:
                        return res
                    
                    for i, j in dire:
                        nx, ny = b[0] + i, b[1] + j
                        if check1(nx, ny) and \
                            check1(b[0] - i, b[1] - j) and\
                            ((nx, ny), b) not in vis and \
                            canMoveTo((b[0] - i, b[1] - j), b, [p], set([p])):
                            q.append(((nx, ny), b))
                            vis.add(((nx, ny), b))
                res += 1
            return -1

        return move(T, [(B, S)], set([(B, S)]))

上面代码的思路非常清晰。但是我们实现上可以将状态简化,我们可以通过箱子的坐标和箱子移动方向作为状态,这样我们原先需要160000种状态,而现在只需要1600种状态。这么做可以改善空间复杂度,但是无法改进时间复杂度,代码上也没有上面简洁,所以我这里就不写出来了。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

THE END

发表回复