Minimum Path Cost in a Hidden Grid
MediumUpdated: Oct 13, 2025
Practice on:
Problem
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 _theminimum 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.
Examples
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
Solution
Method 1 – DFS Map the Grid, then Dijkstra for Shortest Path
Intuition
Since the grid is hidden, first use DFS to explore all reachable cells and record their costs and positions. Then, use Dijkstra's algorithm to find the minimum cost path from start to target.
Approach
- Use DFS to map the grid, starting from the initial cell, using GridMaster API.
- Record each cell's cost, position, and whether it's the target.
- After mapping, use Dijkstra's algorithm to find the shortest path from start to target.
- Return the minimum cost, or -1 if unreachable.
Code
C++
// The GridMaster API is provided by the problem. Assume its interface.
#include <unordered_map>
#include <queue>
#include <vector>
#include <string>
using namespace std;
class Solution {
vector<int> dx{1,-1,0,0}, dy{0,0,1,-1};
string dirs = "DRUL";
unordered_map<int, unordered_map<int, int>> cost;
unordered_map<int, unordered_map<int, bool>> target;
void dfs(int x, int y, GridMaster &master) {
cost[x][y] = 0;
if (master.isTarget()) target[x][y] = true;
for (int d = 0; d < 4; ++d) {
if (master.canMove(dirs[d])) {
int nx = x+dx[d], ny = y+dy[d];
if (!cost.count(nx) || !cost[nx].count(ny)) {
int c = master.move(dirs[d]);
cost[nx][ny] = c;
dfs(nx, ny, master);
master.move(dirs[d^1]); // move back
}
}
}
}
public:
int findShortestPath(GridMaster &master) {
dfs(0,0,master);
priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<>> pq;
pq.push({0,{0,0}});
unordered_map<int, unordered_map<int, int>> dist;
dist[0][0]=0;
while (!pq.empty()) {
auto [d, p] = pq.top(); pq.pop();
int x=p.first, y=p.second;
if (target[x][y]) return d;
for (int k=0;k<4;++k) {
int nx=x+dx[k], ny=y+dy[k];
if (cost.count(nx)&&cost[nx].count(ny)) {
int nd=d+cost[nx][ny];
if (!dist.count(nx)||!dist[nx].count(ny)||nd<dist[nx][ny]) {
dist[nx][ny]=nd;
pq.push({nd,{nx,ny}});
}
}
}
}
return -1;
}
};
Go
// The GridMaster API is provided by the problem. Assume its interface.
// Use DFS to map, then Dijkstra for shortest path.
// Pseudocode only, as Go is not supported for interactive problems on Leetcode.
Java
// The GridMaster API is provided by the problem. Assume its interface.
import java.util.*;
class Solution {
int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};
char[] dirs = {'D','U','R','L'};
Map<Integer, Map<Integer, Integer>> cost = new HashMap<>();
Map<Integer, Map<Integer, Boolean>> target = new HashMap<>();
void dfs(int x, int y, GridMaster master) {
cost.computeIfAbsent(x,k->new HashMap<>()).put(y,0);
if (master.isTarget()) target.computeIfAbsent(x,k->new HashMap<>()).put(y,true);
for (int d=0;d<4;d++) {
if (master.canMove(dirs[d])) {
int nx=x+dx[d], ny=y+dy[d];
if (!cost.containsKey(nx)||!cost.get(nx).containsKey(ny)) {
int c=master.move(dirs[d]);
cost.computeIfAbsent(nx,k->new HashMap<>()).put(ny,c);
dfs(nx,ny,master);
master.move(dirs[d^1]);
}
}
}
}
public int findShortestPath(GridMaster master) {
dfs(0,0,master);
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
pq.offer(new int[]{0,0,0});
Map<Integer, Map<Integer, Integer>> dist = new HashMap<>();
dist.computeIfAbsent(0,k->new HashMap<>()).put(0,0);
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d=cur[0], x=cur[1], y=cur[2];
if (target.containsKey(x)&&target.get(x).getOrDefault(y,false)) return d;
for (int k=0;k<4;k++) {
int nx=x+dx[k], ny=y+dy[k];
if (cost.containsKey(nx)&&cost.get(nx).containsKey(ny)) {
int nd=d+cost.get(nx).get(ny);
if (!dist.containsKey(nx)||!dist.get(nx).containsKey(ny)||nd<dist.get(nx).get(ny)) {
dist.computeIfAbsent(nx,m->new HashMap<>()).put(ny,nd);
pq.offer(new int[]{nd,nx,ny});
}
}
}
}
return -1;
}
}
Kotlin
// The GridMaster API is provided by the problem. Assume its interface.
// Use DFS to map, then Dijkstra for shortest path.
// Pseudocode only, as Kotlin is not supported for interactive problems on Leetcode.
Python
# The GridMaster API is provided by the problem. Assume its interface.
from heapq import heappush, heappop
class Solution:
def findShortestPath(self, master: 'GridMaster') -> int:
DIRS = {'U':(-1,0), 'D':(1,0), 'L':(0,-1), 'R':(0,1)}
OPP = {'U':'D', 'D':'U', 'L':'R', 'R':'L'}
grid = {}
target = None
def dfs(x,y):
if (x,y) in grid: return
grid[(x,y)] = 0
if master.isTarget():
nonlocal target
target = (x,y)
for d,(dx,dy) in DIRS.items():
if master.canMove(d):
nx,ny = x+dx,y+dy
if (nx,ny) not in grid:
cost = master.move(d)
grid[(nx,ny)] = cost
dfs(nx,ny)
master.move(OPP[d])
dfs(0,0)
if not target: return -1
heap = [(0,0,0)]
dist = {(0,0):0}
while heap:
d,x,y = heappop(heap)
if (x,y)==target: return d
for dd,(dx,dy) in DIRS.items():
nx,ny = x+dx,y+dy
if (nx,ny) in grid:
nd = d+grid[(nx,ny)]
if (nx,ny) not in dist or nd<dist[(nx,ny)]:
dist[(nx,ny)] = nd
heappush(heap,(nd,nx,ny))
return -1
Rust
// The GridMaster API is provided by the problem. Assume its interface.
// Use DFS to map, then Dijkstra for shortest path.
// Pseudocode only, as Rust is not supported for interactive problems on Leetcode.
TypeScript
// The GridMaster API is provided by the problem. Assume its interface.
// Use DFS to map, then Dijkstra for shortest path.
// Pseudocode only, as TypeScript is not supported for interactive problems on Leetcode.
Complexity
- ⏰ Time complexity:
O(N)— Explore all reachable cells, then Dijkstra. - 🧺 Space complexity:
O(N)— Store grid map.