跳转至

LeetCode: 505. 迷宫II

1、题目描述

由空地和墙组成的迷宫中有一个。球可以向上下左右四个方向滚动,但在遇到墙壁前不会停止滚动。当球停下时,可以选择下一个方向。

给定球的起始位置,目的地和迷宫,找出让球停在目的地的最短距离。距离的定义是球从起始位置(不包括)到目的地(包括)经过的空地个数。如果球无法停在目的地,返回 -1

迷宫由一个01的二维数组表示。 1表示墙壁,0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。

示例 1:

输入 1: 迷宫由以下二维数组表示

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)

输出: 12

解析: 一条最短路径 : left -> down -> left -> down -> right -> down -> right。
             总距离为 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12。

img

示例 2:

输入 1: 迷宫由以下二维数组表示

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (3, 2)

输出: -1

解析: 没有能够使球停在目的地的路径。

img

注意:

  • 迷宫中只有一个球和一个目的地。
  • 球和目的地都在空地上,且初始时它们不在同一位置。
  • 给定的迷宫不包括边界 (如图中的红色矩形), 但你可以假设迷宫的边缘都是墙壁。
  • 迷宫至少包括2块空地,行数和列数均不超过100

2、解题思路

  • 初始化起始点到其它位置的距离都为无穷

  • 每次检查上下左右能否前进并且停住,并判断是否能降低起始点到当前点的距离,能的话加入队列搜索

from functools import lru_cache
from collections import deque, defaultdict


class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        row, col = len(maze), len(maze[0])

        # 坐标验证
        def available(m, n):
            return 0 <= m < row and 0 <= n < col

        @lru_cache(None)
        def get_next(pos, direction):
            next_pos = [-1, -1]
            steps = 1
            if direction == 1:
                if not available(pos[0], pos[1] + 1) or maze[pos[0]][pos[1] + 1] == 1:
                    return next_pos
                next_pos = [pos[0], pos[1] + 1]
                while next_pos[1] + 1 < col and maze[next_pos[0]][next_pos[1] + 1] == 0:
                    next_pos[1] += 1
                    steps += 1
            elif direction == 2:
                if not available(pos[0] + 1, pos[1]) or maze[pos[0] + 1][pos[1]] == 1:
                    return next_pos
                next_pos = [pos[0] + 1, pos[1]]
                while next_pos[0] + 1 < row and maze[next_pos[0] + 1][next_pos[1]] == 0:
                    next_pos[0] += 1
                    steps += 1
            elif direction == 3:
                if not available(pos[0], pos[1] - 1) or maze[pos[0]][pos[1] - 1] == 1:
                    return next_pos
                next_pos = [pos[0], pos[1] - 1]
                while next_pos[1] - 1 >= 0 and maze[next_pos[0]][next_pos[1] - 1] == 0:
                    next_pos[1] -= 1
                    steps += 1
            elif direction == 4:
                if not available(pos[0] - 1, pos[1]) or maze[pos[0] - 1][pos[1]] == 1:
                    return next_pos
                next_pos = [pos[0] - 1, pos[1]]
                while next_pos[0] - 1 >= 0 and maze[next_pos[0] - 1][next_pos[1]] == 0:
                    next_pos[0] -= 1
                    steps += 1
            return next_pos[0], next_pos[1], steps

        mem = defaultdict(lambda: float('inf'))
        mem[tuple(start)] = 0
        d = deque()
        d.append(tuple(start + [0]))
        ans = float('inf')
        while d:
            cur = d.popleft()
            if (cur[0], cur[1]) == tuple(destination):
                ans = min(ans, cur[2])
                continue

            for i in range(1, 5):
                temp = get_next(cur[:2], i)
                if temp[0] != -1 and mem[temp[:2]] > cur[2] + temp[2]:
                    d.append((temp[0], temp[1], cur[2] + temp[2]))
                    mem[temp[:2]] = cur[2] + temp[2]

        return ans if ans != float('inf') else -1