Shortest Path in a Hidden Grid
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.
You want to find the minimum distance 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.
Thr GridMaster class has the following functions:
boolean canMove(char direction)Returnstrueif the robot can move in that direction. Otherwise, it returnsfalse.void move(char direction)Moves the robot in that direction. If this move would move the robot to a blocked cell or off the grid, the move will be ignored , and the robot will remain in the same position.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 distance between the robot's initial starting cell and 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 where:
grid[i][j] == -1indicates that the robot is in cell(i, j)(the starting cell).grid[i][j] == 0indicates that the cell(i, j)is blocked.grid[i][j] == 1indicates that the cell(i, j)is empty.grid[i][j] == 2indicates that the cell(i, j)is the target cell.
There is exactly one -1 and 2 in grid. Remember that you will not have this information in your code.
Examples
Example 1:
Input: grid = [[1,2],[-1,0]]
Output: 2
Explanation: One possible interaction is described below:
The robot is initially standing on cell (1, 0), denoted by the -1.
- master.canMove('U') returns true.
- master.canMove('D') returns false.
- master.canMove('L') returns false.
- master.canMove('R') returns false.
- master.move('U') moves the robot to the cell (0, 0).
- 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('R') moves the robot to the cell (0, 1).
- master.isTarget() returns true.
We now know that the target is the cell (0, 1), and the shortest path to the target cell is 2.
Example 2:
Input: grid = [[0,0,-1],[1,1,1],[2,0,0]]
Output: 4
Explanation: The minimum distance between the robot and the target cell is 4.
Example 3:
Input: grid = [[-1,0],[0,2]]
Output: -1
Explanation: There is no path from the robot to the target cell.
Constraints:
1 <= n, m <= 500m == grid.lengthn == grid[i].lengthgrid[i][j]is either-1,0,1, or2.- There is exactly one
-1ingrid. - There is exactly one
2ingrid.
Solution
Method 1 – DFS Mapping + BFS Shortest Path
Intuition
Since the grid is hidden, we must first explore all reachable cells using DFS, mapping the accessible area and locating the target. Then, we use BFS from the start to the target to find the shortest path.
Approach
- Use DFS to explore the grid, starting from the initial cell, using
canMoveandmoveto traverse, and record the accessible cells and the target's location. - After mapping, use BFS from the start to the target to compute the shortest path.
- If the target is unreachable, return -1.
Code
Java
import java.util.*;
// This is the GridMaster's API interface.
// You should not implement it, or speculate about its implementation
interface GridMaster {
public boolean canMove(char direction);
public void move(char direction);
public boolean isTarget();
}
class Solution {
int[] dx = {-1,1,0,0};
int[] dy = {0,0,-1,1};
char[] dirs = {'U','D','L','R'};
char[] rev = {'D','U','R','L'};
int N = 1001, offset = 500;
boolean[][] vis = new boolean[N][N];
boolean[][] grid = new boolean[N][N];
int tx = -1, ty = -1;
public int findShortestPath(GridMaster master) {
dfs(offset, offset, master);
if (tx==-1) return -1;
Queue<int[]> q = new LinkedList<>();
boolean[][] seen = new boolean[N][N];
q.offer(new int[]{offset, offset, 0});
seen[offset][offset]=true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int x=cur[0], y=cur[1], d=cur[2];
if (x==tx && y==ty) return d;
for (int i=0;i<4;++i) {
int nx=x+dx[i], ny=y+dy[i];
if (grid[nx][ny] && !seen[nx][ny]) {
seen[nx][ny]=true;
q.offer(new int[]{nx,ny,d+1});
}
}
}
return -1;
}
void dfs(int x, int y, GridMaster master) {
vis[x][y]=true;
grid[x][y]=true;
if (master.isTarget()) { tx=x; ty=y; }
for (int i=0;i<4;++i) {
int nx=x+dx[i], ny=y+dy[i];
if (!vis[nx][ny] && master.canMove(dirs[i])) {
master.move(dirs[i]);
dfs(nx,ny,master);
master.move(rev[i]);
}
}
}
}
Python
# This is the GridMaster's API interface.
# You should not implement it, or speculate about its implementation
# class GridMaster:
# def canMove(self, direction: str) -> bool: ...
# def move(self, direction: str) -> None: ...
# def isTarget(self) -> bool: ...
class Solution:
def findShortestPath(self, master: 'GridMaster') -> int:
N, offset = 1001, 500
grid = [[0]*N for _ in range(N)]
vis = [[False]*N for _ in range(N)]
tx = ty = -1
dirs = ['U','D','L','R']
dx = [-1,1,0,0]
dy = [0,0,-1,1]
rev = {'U':'D','D':'U','L':'R','R':'L'}
def dfs(x,y):
nonlocal tx, ty
vis[x][y]=True
grid[x][y]=1
if master.isTarget():
tx, ty = x, y
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if not vis[nx][ny] and master.canMove(dirs[i]):
master.move(dirs[i])
dfs(nx,ny)
master.move(rev[dirs[i]])
dfs(offset, offset)
if tx==-1: return -1
from collections import deque
q = deque([(offset, offset, 0)])
seen = [[False]*N for _ in range(N)]
seen[offset][offset]=True
while q:
x,y,d = q.popleft()
if (x,y)==(tx,ty): return d
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if grid[nx][ny] and not seen[nx][ny]:
seen[nx][ny]=True
q.append((nx,ny,d+1))
return -1
Complexity
- ⏰ Time complexity:
O(A)— Where A is the number of accessible cells (DFS + BFS each visit each cell once). - 🧺 Space complexity:
O(A)— For the mapped grid and visited arrays.