# LeetCode: 490. 迷宫¶

## 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: 迷宫由以下二维数组表示

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

class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
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]
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
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
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

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
return next_pos

mem = set(tuple(start))

d = deque()
d.append(tuple(start))
while d:
cur = d.popleft()
if cur == tuple(destination):
return True

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