Watch 3 video solutions for Shortest Path in a Hidden Grid, a medium level problem involving Depth-First Search, Breadth-First Search, Graph. This walkthrough by Cracking FAANG has 2,182 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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) Returns true if the robot can move in that direction. Otherwise, it returns false.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() Returns true if the robot is currently on the target cell. Otherwise, it returns false.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 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] == -1 indicates that the robot is in cell (i, j) (the starting cell).grid[i][j] == 0 indicates that the cell (i, j) is blocked.grid[i][j] == 1 indicates that the cell (i, j) is empty.grid[i][j] == 2 indicates 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.
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, or 2.-1 in grid.2 in grid.Problem Overview: You control a robot in a grid where the layout is hidden. The robot can move in four directions and only knows whether a move is valid after attempting it. The goal is to discover the grid and compute the shortest path from the start cell to the target.
Approach 1: Blind BFS Exploration (Conceptual Baseline) (Time: O(N), Space: O(N))
A direct idea is to run breadth-first search while exploring the grid. BFS normally guarantees the shortest path, but the hidden environment makes this difficult. Each time you explore a neighbor, the robot must physically move and possibly backtrack to maintain BFS order. This results in complex state management because BFS assumes random access to neighbors, while the robot only moves locally. Theoretically the exploration still touches each reachable cell once, giving O(N) time and space, but the implementation becomes messy due to heavy movement and backtracking.
Approach 2: DFS for Graph Construction + BFS for Shortest Path (Time: O(N), Space: O(N))
A cleaner strategy separates exploration from path computation. First run depth-first search to fully explore the grid. From the starting cell, attempt all four directions using the robot API. If a move succeeds, record the new coordinate in a map (for example a HashMap or set) and continue DFS recursively. After exploring a direction, move the robot back to the previous cell to restore position. This DFS builds an explicit graph representation of all reachable cells and marks the target location when discovered.
Once the grid structure is known, run a standard BFS on the discovered graph. Start from (0,0), push neighbors into a queue, and track visited cells. BFS guarantees the shortest number of moves to the target because each level represents one step farther from the start. The grid size explored by DFS determines the complexity, so both DFS exploration and BFS traversal take O(N) time with O(N) memory where N is the number of reachable cells.
This separation of responsibilities makes the code far easier to reason about. DFS handles robot movement and map discovery. BFS handles shortest-path logic on the constructed graph.
Recommended for interviews: DFS for exploration followed by BFS for shortest path is the expected solution. The baseline idea of exploring while searching shows intuition, but interviewers look for the insight that mapping the grid first simplifies the shortest-path computation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Blind BFS Exploration with Robot Movement | O(N) | O(N) | Conceptual approach when attempting to directly compute shortest path during exploration, but implementation becomes complex. |
| DFS Grid Discovery + BFS Shortest Path | O(N) | O(N) | Best practical approach. First map the hidden grid with DFS, then run BFS on the discovered graph to compute the shortest path. |