# 68ms python BFS solution

• This question is actually quit straight forward, the only thing needs to pay attention is the visited map (stores which cell in the maze has been visited), I was using a `set` at first, but it doesn't guarantee the best solution, therefore we should use a map to store the best distance to reach current cell from starting point, if we visit the same position again with a smaller distance, we should update the map.

``````from collections import deque, defaultdict

class Solution(object):
def findShortestWay(self, maze, ball, hole):
result = []
self.min_distance = 0x7fffffff
# {position_of_ball: best_distance_to_reach_here}
visited = defaultdict(int)
max_row, max_col = len(maze), len(maze[0])

def move(row, col, ball, distance):
"""if found, return hole position, else until the end, row col [+/-1]"""
tmp = ball
while 0 <= ball[0] + row < max_row and 0 <= ball[1] + col < max_col and maze[ball[0] + row][ball[1] + col] == 0:
distance += 1
ball = (ball[0] + row, ball[1] + col)
# break early if current distance has already worse than the best solution
if distance > self.min_distance:
return None, None
if ball == hole:
return ball, distance
# if the ball is not moving, ignore this direction by return None, None
if tmp == ball:
return None, None
return ball, distance

def helper(initial_ball):
directions = [
('d', (1, 0)),
('u', (-1, 0)),
('l', (0, -1)),
('r', (0, 1)),
]
queue = deque([(tuple(initial_ball), 0, "")])
while queue:
ball, distance, path = queue.popleft()
if ball not in visited:
visited[ball] = distance
else:
visited[ball] = min(visited[ball], distance)
for name, direction in directions:
newball, newdistance = move(direction[0], direction[1], ball, distance)
if newball is None:
continue
# print newball
if newball == hole:
if newdistance <= self.min_distance:
self.min_distance = newdistance
result.append((path + name, newdistance))
else:
if newball not in visited or newdistance <= visited[newball]:
queue.append((newball, newdistance, path + name))

hole = tuple(hole)
helper(ball)
if not result:
return "impossible"
result.sort(key=lambda x: x[0])
return min(result, key=lambda x: x[1])[0]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.