1from collections import namedtuple
2class Solution:
3 coord = namedtuple("coord", ("i", "j"))
4 def searchMaze(self, maze, s, e):
5 global coord
6 curr = coord(s[0], s[1])
7 path = []
8 return self.dfs(maze, s, e, curr, path)
9
10 def dfs(self, maze, s, e, curr, path):
11 if curr.i < 0 or curr.i >= len(maze) or curr.j < 0 or curr.j >= len(maze[0]) or maze[curr.i][curr.j] != 0: return False
12 path.append(curr)
13 maze[curr.i][curr.j] = 1
14 if curr == e: return True
15
16 if self.dfs(maze, s, e, coord(curr.i - 1, curr.j), path): return True
17 if self.dfs(maze, s, e, coord(curr.i + 1, curr.j), path): return True
18 if self.dfs(maze, s, e, coord(curr.i, curr.j - 1), path): return True
19 if self.dfs(maze, s, e, coord(curr.i, curr.j + 1), path): return True
20 del path[-1]
21
22 return False