499. The Maze III - cocoder39/coco39_LC GitHub Wiki

499. The Maze III

Option 1:

• 第一层：最短路径问题
• 第二层：不是每一个grid都是一个node, 只有边界上的点和hole才是node. (ball在起始时是一个node，此后就不再算作有效node). 这样做的好处就是每一个node都是stateless, 不需要考虑方向
• 第三层：使用heap时，需要考虑lexicographically order
• 第四层：使用dist时，需要考虑lexicographically order

class Solution:
    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
        
        DIRECTIONS = [(-1, 0, 'u'), (1, 0, 'd'), (0, -1, 'l'), (0, 1, 'r')]
        m, n = len(maze), len(maze[0])
        dist = {(ball[0], ball[1]): (0, '')}
        pq = [(0, '', ball[0], ball[1])]
        res = "impossible"
        
        while pq:
            distance, path, row, col = heapq.heappop(pq)
            if row == hole[0] and col == hole[1]:
                return path
            
            for dx, dy, d in DIRECTIONS:
                newRow, newCol, newDistance = row, col, distance
                newPath = path + d
                while 0 <= newRow + dx < m and 0 <= newCol + dy < n and maze[newRow + dx][newCol + dy] == 0:
                    newRow += dx
                    newCol += dy
                    newDistance += 1
                    if newRow == hole[0] and newCol == hole[1]:
                        break
                        
                if (newRow, newCol) not in dist or (newDistance, newPath) < dist[(newRow, newCol)]:
                    dist[(newRow, newCol)] = (newDistance, newPath)
                    heapq.heappush(pq, (newDistance, newPath, newRow, newCol))
        
        return res

Option 2: BFS

每个状态由grid的坐标和方向决定

time complexity: O(M * N) 每一个点最多被访问4次（4 directions）

class Solution:
    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
        m, n = len(maze), len(maze[0])
        DIRECTIONS = {'u': (-1, 0), 'd': (1, 0), 'l': (0, -1), 'r': (0, 1)}
        res = (float("inf"), "impossible")
        visited = set()
        queue = collections.deque()
        
        for direction in DIRECTIONS:
            dx, dy = DIRECTIONS[direction]
            nextRow, nextCol = ball[0] + dx, ball[1] + dy
            if 0 <= nextRow < m and 0 <= nextCol < n and maze[nextRow][nextCol] == 0:
                queue.append((ball[0], ball[1], 0, direction, direction))
        
        while queue:
            row, col, distance, path, direction = queue.popleft()
            visited.add((row, col, direction))
                
            if row == hole[0] and col == hole[1]:
                res = min(res, (distance, path))
                continue
                
            dx, dy = DIRECTIONS[direction]
            if 0 <= row + dx < m and 0 <= col + dy < n and maze[row+dx][col+dy] == 0:
                if (row+dx, col+dy, direction) not in visited:
                    queue.append((row+dx, col+dy, distance+1, path, direction))
            else:
                for d in DIRECTIONS:
                    dx, dy = DIRECTIONS[d]
                    if 0 <= row + dx < m and 0 <= col + dy < n and maze[row+dx][col+dy] == 0 and (row+dx, col+dy, d) not in visited:
                        queue.append((row+dx, col+dy, distance+1, path+d, d))
        
        return res[1]