# Easy python BFS solution without using heap O(n) complexity instead of O(nlog(n))

• Just simply do BFS. But for repeat check, instead of only check position, we check (moving_direction, position) pair.
If the ball is going to stop, we change its moving_direction to (0, 0).

`````` class Solution(object):
def findShortestWay(self, maze, ball, hole):
"""
:type maze: List[List[int]]
:type ball: List[int]
:type hole: List[int]
:rtype: str
"""
q = [ ((0, 0), tuple(ball), 0, "")]
dir_dict = {(1, 0): "d", (-1, 0): "u", (0, 1):"r", (0, -1):"l"}
self.visited = set((q[0][0], q[0][1]))
for n in q:
direction, pos, dis, path = n
if pos == tuple(hole):
return path
next_directions = []
if direction == (0, 0):
next_directions = [(1, 0), (0, -1), (0, 1), (-1, 0)]
else:
next_directions = [direction]

for next_direction in next_directions:
dir_name = dir_dict[next_direction] if add_path else ""
next_pos = (pos[0] + next_direction[0], pos[1] + next_direction[1])
next_next_pos = (next_pos[0] + next_direction[0], next_pos[1] + next_direction[1])
if 0 <= next_pos[0] < len(maze) and 0 <= next_pos[1] < len(maze[0]) and maze[next_pos[0]][next_pos[1]] != 1:
if next_next_pos[0] < 0 or next_next_pos[0] >= len(maze) or \
next_next_pos[1] < 0 or next_next_pos[1] >= len(maze[0]) or \
maze[next_next_pos[0]][next_next_pos[1]] == 1:
next_direction = (0, 0)
next = (next_direction, next_pos, dis + 1, path + dir_name)
if (next[0], next[1]) not in self.visited:
q.append(next)