Minimum Path Cost in a Hidden Grid - Video Solutions
1810. Minimum Path Cost in a Hidden Grid (Leetcode Medium)
Minimum Path Cost in a Hidden Grid - Video Solution
Watch 3 video solutions for Minimum Path Cost in a Hidden Grid, a medium level problem involving Depth-First Search, Breadth-First Search, Graph. This walkthrough by Programming Live with Larry has 497 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
This is an interactive problem.
There is a robot in a hidden grid, and you are trying to get it from its starting cell to the target cell in this grid. The grid is of size m x n, and each cell in the grid is either empty or blocked. It is guaranteed that the starting cell and the target cell are different, and neither of them is blocked.
Each cell has a cost that you need to pay each time you move to the cell. The starting cell's cost is not applied before the robot moves.
You want to find the minimum total cost to move the robot to the target cell. However, you do not know the grid's dimensions, the starting cell, nor the target cell. You are only allowed to ask queries to the GridMaster object.
The GridMaster class has the following functions:
boolean canMove(char direction)Returnstrueif the robot can move in that direction. Otherwise, it returnsfalse.int move(char direction)Moves the robot in that direction and returns the cost of moving to that cell. If this move would move the robot to a blocked cell or off the grid, the move will be ignored, the robot will remain in the same position, and the function will return-1.boolean isTarget()Returnstrueif the robot is currently on the target cell. Otherwise, it returnsfalse.
Note that direction in the above functions should be a character from {'U','D','L','R'}, representing the directions up, down, left, and right, respectively.
Return the minimum total cost to get the robot from its initial starting cell to the target cell. If there is no valid path between the cells, return -1.
Custom testing:
The test input is read as a 2D matrix grid of size m x n and four integers r1, c1, r2, and c2 where:
grid[i][j] == 0indicates that the cell(i, j)is blocked.grid[i][j] >= 1indicates that the cell(i, j)is empty andgrid[i][j]is the cost to move to that cell.(r1, c1)is the starting cell of the robot.(r2, c2)is the target cell of the robot.
Remember that you will not have this information in your code.
Example 1:
Input: grid = [[2,3],[1,1]], r1 = 0, c1 = 1, r2 = 1, c2 = 0
Output: 2
Explanation: One possible interaction is described below:
The robot is initially standing on cell (0, 1), denoted by the 3.
- master.canMove('U') returns false.
- master.canMove('D') returns true.
- master.canMove('L') returns true.
- master.canMove('R') returns false.
- master.move('L') moves the robot to the cell (0, 0) and returns 2.
- master.isTarget() returns false.
- master.canMove('U') returns false.
- master.canMove('D') returns true.
- master.canMove('L') returns false.
- master.canMove('R') returns true.
- master.move('D') moves the robot to the cell (1, 0) and returns 1.
- master.isTarget() returns true.
- master.move('L') doesn't move the robot and returns -1.
- master.move('R') moves the robot to the cell (1, 1) and returns 1.
We now know that the target is the cell (1, 0), and the minimum total cost to reach it is 2.
Example 2:
Input: grid = [[0,3,1],[3,4,2],[1,2,0]], r1 = 2, c1 = 0, r2 = 0, c2 = 2 Output: 9 Explanation: The minimum cost path is (2,0) -> (2,1) -> (1,1) -> (1,2) -> (0,2).
Example 3:
Input: grid = [[1,0],[0,1]], r1 = 0, c1 = 0, r2 = 1, c2 = 1 Output: -1 Explanation: There is no path from the robot to the target cell.
Constraints:
1 <= n, m <= 100m == grid.lengthn == grid[i].length0 <= grid[i][j] <= 100
Approach Overview
Problem Overview: The grid is hidden and can only be explored through an interactive API that allows movement and returns the cost of entering a cell. Your task is to discover the grid structure and compute the minimum path cost from the start cell to the target cell.
Approach 1: DFS Graph Construction + Heap-Optimized Dijkstra (O(V log V) time, O(V) space)
The grid is unknown at the start, so the first step is exploration. Use Depth-First Search to move through every reachable cell while backtracking to the previous position after exploring each direction. During this exploration, record each cell as a node in a graph and store edges with their movement cost. The DFS effectively converts the hidden grid into a standard weighted graph.
Once the graph is built, run Dijkstra’s shortest path algorithm using a min-heap from Heap (Priority Queue). Initialize the start node with cost 0 and repeatedly expand the node with the smallest accumulated cost. Each edge relaxation updates neighbor distances when a cheaper path is found. This guarantees the optimal path cost to the target because all edge weights are non‑negative.
The key insight is separating the problem into two phases: discovery and optimization. DFS handles the unknown environment while maintaining the correct position using backtracking moves. Dijkstra then works on the discovered graph to compute the true minimum cost efficiently. Time complexity is O(V log V) due to heap operations during shortest path computation, and space complexity is O(V) for storing visited nodes, graph edges, and distances.
Approach 2: DFS Graph Construction + BFS (O(V + E) time, O(V) space)
After building the graph with DFS, you could run Breadth-First Search to find the shortest path if all movement costs were identical. BFS explores nodes level by level and guarantees the minimum number of steps. However, this problem assigns different entry costs to cells, so BFS does not produce the correct minimum-cost path. It’s mainly useful as a conceptual baseline for understanding why a weighted shortest-path algorithm is required.
Recommended for interviews: The DFS exploration followed by Dijkstra’s algorithm is the expected solution. Interviewers want to see that you recognize two separate challenges: discovering the hidden grid and computing a weighted shortest path. Demonstrating DFS with careful backtracking shows control over the interactive environment, while implementing heap-based Dijkstra proves you understand optimal graph traversal for weighted edges.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Exploration + Dijkstra (Priority Queue) | O(V log V) | O(V) | General case with weighted movement costs in the hidden grid |
| DFS Exploration + BFS | O(V + E) | O(V) | Only valid if every move has identical cost |
| DFS Exploration + A* Search | O(E log V) | O(V) | Possible optimization when a heuristic to the target is known |