隐藏网格下的最小消耗路径

这个题解利用了DFS和Dijkstra算法的结合来寻找从起点到目标的最短路径。首先，使用DFS从初始位置开始，探索所有可以移动到的单元格，同时记录每个单元格的移动成本和标记是否为目标。然后，使用Dijkstra算法从起点开始，根据已知的成本和距离，计算到每个可达单元格的最小路径成本。如果找到目标单元格，则返回到该单元格的最小成本。

时间复杂度: O(N + M log M)

空间复杂度: O(N)

# Solution class defining the method to find the shortest path using GridMaster's API

class Solution(object):
    def findShortestPath(self, master: 'GridMaster') -> int:
        dirs = 'DLRU'  # Directions for movement
        dists = [[inf]*201 for _ in range(201)]  # Distance matrix
        costs = [[inf]*201 for _ in range(201)]  # Cost matrix
        dr = dc = inf  # Target row and column
        def dfs(r, c):
            nonlocal dr, dc
            if master.isTarget():  # Check if current cell is the target
                dr, dc = r, c
            for di, (nr, nc) in enumerate([(r+1, c), (r, c-1), (r,c+1), (r-1,c)]):
                d = dirs[di]
                if costs[nr][nc] != inf: continue  # Skip if already visited
                if not master.canMove(d): 
                    costs[nr][nc] = -inf  # Mark as impassable
                else:
                    costs[nr][nc] = master.move(d)  # Move and record cost
                    dfs(nr, nc)  # Recursively visit
                    master.move(dirs[3-di])  # Move back
        sr = sc = 100  # Start at the center of the grid
        costs[100][100] = 0  # Starting point cost is zero
        dfs(100, 100)  # Start DFS from the center
        if dr == inf: return -1  # Return -1 if target is not reachable
        h = [(0,sr, sc)]  # Min-heap for Dijkstra's algorithm
        dists[sr][sc] = 0  # Starting point distance is zero
        while h:
            dist, r, c = heappop(h)  # Pop the least cost cell
            if r == dr and c == dc: return dist  # Return distance if target reached
            for nr, nc in [(r+1, c), (r, c-1), (r,c+1), (r-1,c)]:
                cost = costs[nr][nc]
                if abs(cost) != inf and dists[nr][nc] > dist + cost:
                    dists[nr][nc] = dist + cost  # Update distance
                    heappush(h, (dist + cost, nr, nc))  # Push new distance