leetcode 周赛 163 5266. 推箱子 python 解法

目录

1. 解法

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

游戏地图用大小为 n * m 的网格 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
解释：向下、向左、向左、向上再向上。

示例 4：

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

提示：

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

解法

没时间了我没做，参考别人的做法

排名第 15 的 thuczh 的解法

class Solution(object):
    def minPushBox(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        drct = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        erct = [(0, -1), (0, 1), (-1, 0), (1, 0)]

        def find(x, y, tx, ty, bx, by):
            n = len(grid)
            m = len(grid[0])
            if not (0 <= x < n and 0 <= y < m and 0 <= tx < n and 0 <= ty < m) \
                    or (x == bx and y == by) or (tx == bx and ty == by) \
                    or grid[x][y] == '#' or grid[tx][ty] == '#':
                return False
            if x == tx and y == ty:
                return True

            q = [(x, y)]
            h = set()
            h.add((x, y))
            t = 0
            while t < len(q):
                x, y = q[t]
                t += 1
                for d in drct:
                    xx, yy = x + d[0], y + d[1]
                    if 0 <= xx < n and 0 <= yy < m and (xx, yy) not in h \
                            and grid[xx][yy] != '#' and not (xx == bx and yy == by):
                        if xx == tx and yy == ty:
                            return True
                        q.append((xx, yy))
                        h.add((xx, yy))
            return False

        n = len(grid)
        m = len(grid[0])
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 'S':
                    sx, sy = i, j
                elif grid[i][j] == 'B':
                    bx, by = i, j
                elif grid[i][j] == 'T':
                    tx, ty = i, j
        f = {}
        h = set()
        q = []
        for i in range(4):
            xx, yy = bx + drct[i][0], by + drct[i][1]
            if find(sx, sy, xx, yy, bx, by):
                f[(bx, by, i)] = 0
                q.append((bx, by, i))
                h.add((bx, by, i))

        t = 0
        ret = -1
        while t < len(q):
            x, y, i = q[t]
            t += 1
            sx, sy = (x + drct[i][0], y + drct[i][1])
            if 0 <= ret < f[(x, y, i)]:
                break
            for j in range(4):
                if j != i and ((x, y, j) not in f or f[(x, y, j)] > f[(x, y, i)]) \
                        and find(sx, sy, x + drct[j][0], y + drct[j][1], x, y):
                    f[(x, y, j)] = f[(x, y, i)]
                    if (x, y, j) not in h:
                        h.add((x, y, j))
                        q.append((x, y, j))

            xx, yy = (x + erct[i][0], y + erct[i][1])
            if 0 <= xx < n and 0 <= yy < m and grid[xx][yy] != '#' \
                    and ((xx, yy, i) not in f or f[(xx, yy, i)] > f[(x, y, i)]):
                f[(xx, yy, i)] = f[(x, y, i)] + 1
                if xx == tx and yy == ty and (ret == -1 or ret > f[(xx, yy, i)]):
                    ret = f[(xx, yy, i)]
                if (xx, yy, i) not in h:
                    h.add((xx, yy, i))
                    q.append((xx, yy, i))
        return ret

周赛163排名第 10 的 kariters 的解法

class Solution(object):
    def minPushBox(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        def get_pos(c):
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    if grid[i][j] == c:
                        return i,j
        n = len(grid)
        m = len(grid[0])
        rs = get_pos('S')
        xs = get_pos('B')
        ts = get_pos('T')
        s  = (rs, xs, 0)
        mx = [-1,0,0,1]
        my = [0,-1,1,0]
        q = [s]
        def judeg(x,y):
            if x < 0 or x >= n or y < 0 or y >= m:
                return False
            if grid[x][y] == '#':
                return False
            return True
        vis = [ [-1]*2500 for _ in range(2500)]
        def j_vis(rs, bs, step):
            s1 = 100 * rs[0] + rs[1]
            s2 = 100 * bs[0] + bs[1]
            if vis[s1][s2] == -1:
                vis[s1][s2] = step
                return True
            if step >= vis[s1][s2]:
                return False
            vis[s1][s2] = step
            return True
        ret = -1
        while len(q)>0:
            rs, xs, step = q.pop(0)
            if xs[0] == ts[0] and xs[1] == ts[1]:
                if ret == -1:
                    ret = step
                ret = min(ret,step)
            for i in range(4):
                tx = rs[0] + mx[i]
                ty = rs[1] + my[i]
                if not judeg(tx,ty):
                    continue

                if tx == xs[0] and ty == xs[1]:
                    xtx = xs[0] + mx[i]
                    xty = xs[1] + my[i]
                    if not judeg(xtx,xty):
                        continue
                    new_xs = (xtx,xty)
                    f = 1
                else:
                    new_xs = (xs[0], xs[1])
                    f = 0
                new_rs = (tx,ty)
                if j_vis(new_rs, new_xs, step+f):
                    q.append(((tx,ty),new_xs,step+f))

        return ret