Python PriorityQueue Solution


  • 0
    D
    from Queue import PriorityQueue
    class Solution(object):
        def shortestDistance(self, maze, start, destination):
            """
            :type maze: List[List[int]]
            :type start: List[int]
            :type destination: List[int]
            :rtype: int
            """
            visited = set()
            m, n = len(maze), len(maze[0])
            queue = PriorityQueue()
            queue.put((0, tuple(start)))
            dis = [None]
            while not queue.empty():
                next_tgt = queue.get()
                pos, curr_dis = next_tgt[1], next_tgt[0]
                if pos in visited: continue
                if pos == tuple(destination):
                    dis[0] = curr_dis
                    break
                visited.add(pos)
                i, j = pos
                right_j = left_j = j
                up_i = down_i = i
                while right_j < n and maze[i][right_j] == 0: right_j += 1
                while left_j >= 0 and maze[i][left_j] == 0: left_j -= 1
                while down_i < m and maze[down_i][j] == 0: down_i += 1
                while up_i >= 0 and maze[up_i][j] == 0: up_i -= 1
                queue.put((curr_dis + right_j - 1 - j, (i, right_j-1)))
                queue.put((curr_dis + j - 1 - left_j, (i, left_j+1)))
                queue.put((curr_dis+ i - 1 - up_i, (up_i+1, j)))
                queue.put((curr_dis + down_i - 1 - i, (down_i-1, j)))
                
            return dis[0] if dis[0] else -1
                
                
                
                    
                
    

  • 0
    P

    Hi, I am trying to re-implement it using deque in python. The code is like

    class Solution(object):
        def shortestDistance(self, maze, start, destination):
            """
            :type maze: List[List[int]]
            :type start: List[int]
            :type destination: List[int]
            :rtype: int
            """
            # BFS
            visited = set()
            m, n = len(maze), len(maze[0])
            q = collections.deque([(0, tuple(start))])
            dis = None
            while q:
                curr_dis, pos = q.popleft()
                if pos in visited: continue
                if pos == tuple(destination):
                    dis = curr_dis
                    break
                visited.add(pos)
                i, j = pos
                right_j = left_j = j
                up_i = down_i = i
                while right_j < n and maze[i][right_j] == 0: right_j += 1
                while left_j >= 0 and maze[i][left_j] == 0: left_j -= 1
                while down_i < m and maze[down_i][j] == 0: down_i += 1
                while up_i >= 0 and maze[up_i][j] == 0: up_i -= 1
                q.append((curr_dis + right_j - 1 - j, (i, right_j-1)))
                q.append((curr_dis + j - 1 - left_j, (i, left_j+1)))
                q.append((curr_dis+ i - 1 - up_i, (up_i+1, j)))
                q.append((curr_dis + down_i - 1 - i, (down_i-1, j)))
                
            return dis if dis else -1
    

    but it does not pass all the tests( failed at test 68). Can anyone lend me a hand? thanks!


Log in to reply
 

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