1263：推箱子（2297 分）

Ian

2019-11-17 约 656 字预计阅读 2 分钟次阅读

力扣第 163 场周赛第 4 题

题目

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

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

分析

将 (玩家位置，箱子位置) 看作状态，即是典型的最短路问题
每次状态转移的成本为 0 或 1，因此用 01bfs 即可
- 01bfs 和 dijkstra 的区别仅在于一个用队列，一个用堆

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        d = {grid[i][j]:(i,j) for i in range(m) for j in range(n)}
        (si,sj),(bi,bj), T = d['S'], d['B'], d['T']
        Q = deque([(0,si,sj,bi,bj)])
        d = defaultdict(lambda:inf)
        d[(si,sj,bi,bj)] = 0
        while Q:
            w,si,sj,bi,bj = Q.popleft()
            if (bi,bj)==T:
                return w
            if w>d[(si,sj,bi,bj)]:
                continue
            for di,dj in [(0,-1),(0,1),(1,0),(-1,0)]:
                sx,sy = si+di,sj+dj
                if 0<=sx<m and 0<=sy<n and grid[sx][sy]!='#':
                    if (sx,sy)!=(bi,bj):
                        if w<d[(sx,sy,bi,bj)]:
                            d[(sx,sy,bi,bj)] = w
                            Q.appendleft((w,sx,sy,bi,bj))
                    else:
                        bx,by = bi+di,bj+dj
                        if 0<=bx<m and 0<=by<n and grid[bx][by]!='#':
                            if w+1<d[(sx,sy,bx,by)]:
                                d[(sx,sy,bx,by)] = w+1
                                Q.append((w+1,sx,sy,bx,by))
        return -1

288 ms

目录

1263：推箱子（2297 分）

题目

分析

解答