# Python simple Memoization DFS with comments

• class Solution(object):
def findShortestWay(self, maze, ball, hole):
"""
:type maze: List[List[int]]
:type ball: List[int]
:type hole: List[int]
:rtype: str
"""
self.memo = {}
move = collections.defaultdict(dict)
self.PATH, self.acc = "impossible", float('inf')
m, n = len(maze), len(maze[0]) if maze else 0
# build moving graph for each node
for i, row in enumerate(maze):
for j, wall in enumerate(row):
if wall: continue
up = down = i
while up > 0 and not maze[up-1][j]: up -= 1
while down < m-1 and not maze[down+1][j]: down += 1
left = right = j
while left > 0 and not maze[i][left-1]: left -= 1
while right < n-1 and not maze[i][right+1]: right += 1
if up != i: move[(i, j)]["u"] = ((up, j), i-up)
if down != i: move[(i, j)]["d"] = ((down, j), down-i)
if left != j: move[(i, j)]["l"] = ((i, left), j-left)
if right != j: move[(i, j)]["r"] = ((i, right), right-j)

def dfs((i, j), path, Dist):
# quit current dfs if accumulative distance is bigger than previous
if (i, j) in self.memo and self.memo[(i, j)] < Dist: return
# update memo
self.memo[(i, j)] = Dist
for m in move[(i, j)]:
(I, J), dist = move[(i, j)][m]
# if ball can reach the hole after this move "m"
if (I==i==hole[0] and (J-hole[1])*(j-hole[1]) <= 0) \
or (J==j==hole[1] and (I-hole[0])*(i-hole[0]) <= 0):
last_dist = abs(j-hole[1]) or abs(i-hole[0])