LeetCode Solutions Blog

Minimum Path Cost in a Hidden Grid

Number: 1959

Difficulty: Medium

Paid? Yes

Companies: Meta, Google

Problem Description

A robot is placed in a hidden grid where some cells are blocked and each accessible cell has a movement cost. The grid’s boundaries, layout, starting cell, and target cell are unknown. You interact with the grid only through a GridMaster interface that lets you check if the robot can move in a given direction, actually move (incurring the cost of that cell), and determine if the target has been reached. Your task is to determine the minimum total cost required to move the robot from its starting cell to the target cell. If it is impossible to reach the target, return -1.

Key Insights

Use DFS to explore the entire reachable area from the starting cell by interacting with the GridMaster.
Map every accessible cell along with its associated costs and determine the coordinates of the target cell.
Backtrack appropriately during DFS to reset the state of the robot.
Apply Dijkstra’s algorithm on the mapped graph of accessible cells to compute the shortest path cost from the starting point to the target.

Space and Time Complexity

Time Complexity: O(m * n log(m * n)) where m and n denote the dimensions of the explored grid (DFS visiting each cell and Dijkstra over all cells). Space Complexity: O(m * n) due to storing the mapped grid and auxiliary data structures for DFS and Dijkstra.

Solution

We first run a DFS from the starting cell using the GridMaster interface to explore and map the accessible grid. Each cell is tracked by its relative coordinates with the starting cell at (0, 0). While exploring, we record the cost for moving into each cell, and also note the location of the target cell. After the DFS exploration, we apply Dijkstra’s algorithm on the mapped grid to find the minimum cost path from (0, 0) to the target cell’s coordinate. Key details include:

Using a directions mapping for movement (e.g., 'U', 'D', 'L', 'R') and their corresponding deltas.
Implementing proper backtracking in the DFS to ensure that the robot returns to its previous cell after exploring a branch.
Using a priority queue (min-heap) for Dijkstra’s algorithm to efficiently retrieve the cell with the least current path cost.

Code Solutions

# Python solution with inline comments

import heapq

class Solution:
    def findMinimumPathCost(self, master: 'GridMaster') -> int:
        # mapping for directions and their opposites for backtracking
        directions = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
        opposite = {'U': 'D', 'D': 'U', 'L': 'R', 'R': 'L'}
        
        # gridMap: key is (x,y) and value is the cost to step into that cell
        gridMap = {(0, 0): 0}
        # target location, if found during DFS
        target = [None]
        visited = set()
        
        def dfs(x, y):
            visited.add((x, y))
            # Check if the current cell is the target
            if master.isTarget():
                target[0] = (x, y)
            # Explore all 4 potential directions
            for d in directions:
                dx, dy = directions[d]
                nx, ny = x + dx, y + dy
                # If the next cell is not visited and the robot can move into that cell
                if (nx, ny) not in visited and master.canMove(d):
                    # Move into the cell and obtain the cost
                    cost = master.move(d)
                    # Record the cost received when moving into (nx, ny)
                    gridMap[(nx, ny)] = cost
                    dfs(nx, ny)
                    # Backtrack to previous cell
                    master.move(opposite[d])
        
        # Start DFS exploration from the initial starting cell (0, 0)
        dfs(0, 0)
        
        # If the target was never reached during DFS, return -1
        if target[0] is None:
            return -1
        
        # Use Dijkstra's algorithm to compute the minimum path cost
        start = (0, 0)
        tgt = target[0]
        heap = [(0, start)]  # (current cost, position)
        minCost = {start: 0}
        
        while heap:
            cost, (x, y) = heapq.heappop(heap)
            # If we have reached the target, return the computed cost
            if (x, y) == tgt:
                return cost
            # Check all 4 directions from current cell
            for d in directions:
                dx, dy = directions[d]
                nxt = (x + dx, y + dy)
                if nxt in gridMap:  # if cell was explored
                    newCost = cost + gridMap[nxt]
                    if newCost < minCost.get(nxt, float('inf')):
                        minCost[nxt] = newCost
                        heapq.heappush(heap, (newCost, nxt))
        
        # If target is unreachable based on our map
        return -1