68ms python BFS solution


  • 0
    Z

    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]
    

Log in to reply
 

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