# LeetCode: 505. 迷宫II¶

## 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

总距离为 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12。


输入 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块空地，行数和列数均不超过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