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


  • 0
    Y

    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 = []
                add_path = False
                if direction == (0, 0):
                    next_directions = [(1, 0), (0, -1), (0, 1), (-1, 0)]
                    add_path = True
                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)
                            self.visited.add((next[0], next[1]))
                
            return "impossible"
    

Log in to reply
 

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