Problem statement

https://leetcode.com/problems/minimum-path-cost-in-a-hidden-grid/

Solution

This problem is similar to 1778. Shortest Path in a Hidden Grid: we need to do in two steps:

  1. Run dfs and save traversed graph. Keep it in the form G[x, y] is tuple: cost we need to pay to visit this cell and boolean variable which indicates that it is end node. Notice that we do not need to save starting node, because we will never pay for it.
  2. Perform Dijkstra algorithm on the constructed graph to find the shortest path.

Complexity

Time complexity is O(mn * log(mn)). Space complexity is O(mn).

Code

class Solution(object):
    def findShortestPath(self, master):
        dirs = [("U", -1, 0), ("D", 1, 0), ("L", 0, -1), ("R", 0, 1)]
        back = {"U": "D", "D": "U", "L": "R", "R": "L"}
        G = {}
        
        def dfs(x, y):
            for d, dx, dy in dirs:
                x1, y1 = x + dx, y + dy
                if (x1, y1) not in G and master.canMove(d):
                    cost = master.move(d)
                    G[x1, y1] = (master.isTarget(), cost)
                    dfs(x1, y1)
                    master.move(back[d])
                    
        dfs(0, 0)
        if not G: return -1
        
        dist = {node: float("inf") for node in G}
        dist[0, 0] = 0
        heap = [(0, 0, 0)]

        while heap:
            min_dist, x, y = heappop(heap)
            if G[x, y][0]: return min_dist
            
            for dx, dy in (x+1, y), (x, y+1), (x-1, y), (x, y-1):
                if (dx, dy) not in G: continue
                cand = min_dist + G[dx, dy][1]
                if cand < dist[dx, dy]:
                    dist[dx, dy] = cand
                    heappush(heap, (cand, dx, dy))
                    
        return -1