LeetCode 1778 - Shortest Path in a Hidden Grid

This problem asks us to find the shortest path from a robot's unknown starting position to a hidden target inside a grid. The major challenge is that the grid itself is not directly accessible.

leetcodemediumarraydepth-first-searchbreadth-first-searchmatrixinteractive

LeetCode Problem 1778

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Matrix, Interactive

Solution

Problem Understanding

This problem asks us to find the shortest path from a robot's unknown starting position to a hidden target inside a grid. The major challenge is that the grid itself is not directly accessible. Instead of receiving the matrix as input, we interact with the environment through a GridMaster API.

The robot can only determine local information:

  • canMove(direction) tells whether movement in a direction is possible.
  • move(direction) physically moves the robot.
  • isTarget() tells whether the current cell is the target.

The actual dimensions of the grid are unknown. We do not know where the robot starts, where the target is located, or which cells are blocked. The only way to discover the grid is by exploring it interactively.

The goal is to return the minimum number of moves required to reach the target from the starting position. If the target is unreachable, we return -1.

Although the hidden grid may be as large as 500 x 500, we are only concerned with the reachable region from the starting point. Since we cannot access arbitrary coordinates directly, we must simulate coordinates ourselves while exploring.

The most important observation is that this is effectively a graph traversal problem. Each reachable cell is a node, and edges exist between neighboring walkable cells.

Several edge cases are important:

  • The target may be unreachable even if it exists somewhere in the grid.
  • The reachable region may contain cycles, so revisiting cells without tracking visited states would cause infinite recursion or repeated work.
  • Because movement is physical, every DFS step must carefully backtrack to restore the robot's previous position.
  • The grid boundaries are unknown, so coordinates must be assigned dynamically relative to the starting cell.
  • The target could be adjacent to the starting position or very far away.

Approaches

Brute Force Approach

A naive approach would attempt to repeatedly search for the target while exploring all possible movement sequences from the starting cell.

For example, we could recursively try every possible direction at every step without recording previously visited states. Whenever we move, we continue branching recursively until either the target is found or movement becomes impossible.

This approach is technically correct because it eventually enumerates all reachable paths. However, it is disastrously inefficient because the same cells are revisited repeatedly through different paths. Since the grid can contain cycles, the recursion tree can grow exponentially.

Additionally, because movement is interactive and physical, excessive revisiting creates enormous overhead from repeated API calls.

Optimal Approach

The key insight is that we should separate the problem into two phases:

  1. Discover the reachable portion of the hidden grid using DFS.
  2. Run BFS on the discovered map to compute the shortest path.

DFS is ideal for exploration because it naturally supports backtracking. During exploration:

  • We assign virtual coordinates to cells.
  • We record which cells are reachable.
  • We identify the target location if encountered.

The critical detail is that after exploring a direction recursively, we must physically move the robot back to its previous position. Without this backtracking step, future exploration would start from the wrong location.

Once the reachable grid has been reconstructed, the interactive portion is finished. We now have a standard graph problem. Since all edges have equal weight, BFS guarantees the shortest path.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Repeatedly revisits the same states and paths
Optimal O(V + E) O(V) DFS reconstructs the grid, BFS finds shortest path

Here, V represents the number of reachable cells and E represents adjacency relationships between them.

Algorithm Walkthrough

  1. Start by assigning the robot's initial position the virtual coordinate (0, 0).
  2. Create a DFS function that explores reachable cells. The DFS receives the current virtual coordinates.
  3. Maintain a visited set so we never explore the same virtual coordinate twice. This prevents infinite loops and redundant work.
  4. At each DFS position:
  • Mark the current coordinate as visited.
  • Check master.isTarget().
  • If true, store the target coordinates.
  1. For each of the four directions:
  • Use master.canMove(direction) to determine whether movement is possible.
  • If movement is blocked, skip that direction.
  • Otherwise compute the neighbor coordinates.
  1. If the neighbor has not been visited:
  • Call master.move(direction) to physically move the robot.
  • Recursively DFS into the neighbor.
  • After recursion finishes, move the robot back using the opposite direction.
  1. The backtracking step is essential because DFS assumes recursive calls return to the caller's state. Since the robot physically moves, we must manually restore its previous position.
  2. After DFS completes, we have reconstructed all reachable cells and possibly identified the target location.
  3. If the target was never found, return -1.
  4. Otherwise perform BFS from (0, 0):
  • Use a queue storing (row, col, distance).
  • Expand neighbors level by level.
  • The first time we reach the target coordinate, return the distance.
  1. BFS guarantees the shortest path because every move has equal cost.

Why it works

DFS guarantees that every reachable cell is explored exactly once. Because we correctly backtrack after recursive exploration, the robot's physical position always matches the recursion state.

The discovered map accurately represents the reachable graph. BFS on an unweighted graph always finds the minimum number of edges between two nodes. Therefore, the returned distance is the true shortest path from the start to the target.

Python Solution

from collections import deque
from typing import Dict, Set, Tuple

# """
# This is GridMaster's API interface.
# You should not implement it, or speculate about its implementation
# """
# class GridMaster(object):
#     def canMove(self, direction: str) -> bool:
#         pass
#
#     def move(self, direction: str) -> None:
#         pass
#
#     def isTarget(self) -> bool:
#         pass

class Solution(object):
    def findShortestPath(self, master: 'GridMaster') -> int:
        directions = {
            'U': (-1, 0),
            'D': (1, 0),
            'L': (0, -1),
            'R': (0, 1)
        }

        opposite = {
            'U': 'D',
            'D': 'U',
            'L': 'R',
            'R': 'L'
        }

        reachable = set()
        visited = set()
        target = [None]

        def dfs(row: int, col: int) -> None:
            visited.add((row, col))
            reachable.add((row, col))

            if master.isTarget():
                target[0] = (row, col)

            for direction, (dr, dc) in directions.items():
                next_row = row + dr
                next_col = col + dc

                if (next_row, next_col) in visited:
                    continue

                if not master.canMove(direction):
                    continue

                master.move(direction)

                dfs(next_row, next_col)

                master.move(opposite[direction])

        dfs(0, 0)

        if target[0] is None:
            return -1

        queue = deque([(0, 0, 0)])
        bfs_visited = {(0, 0)}

        while queue:
            row, col, distance = queue.popleft()

            if (row, col) == target[0]:
                return distance

            for dr, dc in directions.values():
                next_row = row + dr
                next_col = col + dc

                if (next_row, next_col) not in reachable:
                    continue

                if (next_row, next_col) in bfs_visited:
                    continue

                bfs_visited.add((next_row, next_col))
                queue.append((next_row, next_col, distance + 1))

        return -1

The implementation is divided into two clear phases.

The first phase reconstructs the hidden grid using DFS. We maintain two sets:

  • visited ensures DFS does not revisit coordinates.
  • reachable stores every accessible cell.

The target variable is stored as a single-element list so nested DFS calls can modify it.

During DFS, we iterate through all four directions. If movement is possible and the neighbor has not been visited, we physically move the robot, recursively explore the neighbor, then backtrack using the opposite direction.

Once exploration completes, the second phase runs BFS on the discovered graph. Since all edges have equal weight, BFS naturally computes the shortest path.

The BFS queue stores coordinates along with the current distance from the starting cell.

Go Solution

/**
 * // This is the GridMaster's API interface.
 * // You should not implement it, or speculate about its implementation
 * type GridMaster struct {
 * }
 *
 * func (this *GridMaster) CanMove(direction byte) bool {}
 * func (this *GridMaster) Move(direction byte) {}
 * func (this *GridMaster) IsTarget() bool {}
 */

type Pair struct {
    row int
    col int
}

type State struct {
    row      int
    col      int
    distance int
}

func findShortestPath(master *GridMaster) int {
    directions := map[byte]Pair{
        'U': {-1, 0},
        'D': {1, 0},
        'L': {0, -1},
        'R': {0, 1},
    }

    opposite := map[byte]byte{
        'U': 'D',
        'D': 'U',
        'L': 'R',
        'R': 'L',
    }

    reachable := make(map[Pair]bool)
    visited := make(map[Pair]bool)

    targetFound := false
    target := Pair{}

    var dfs func(int, int)

    dfs = func(row int, col int) {
        current := Pair{row, col}

        visited[current] = true
        reachable[current] = true

        if master.IsTarget() {
            targetFound = true
            target = current
        }

        for direction, delta := range directions {
            nextRow := row + delta.row
            nextCol := col + delta.col

            next := Pair{nextRow, nextCol}

            if visited[next] {
                continue
            }

            if !master.CanMove(direction) {
                continue
            }

            master.Move(direction)

            dfs(nextRow, nextCol)

            master.Move(opposite[direction])
        }
    }

    dfs(0, 0)

    if !targetFound {
        return -1
    }

    queue := []State{{0, 0, 0}}
    bfsVisited := make(map[Pair]bool)
    bfsVisited[Pair{0, 0}] = true

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]

        if current.row == target.row && current.col == target.col {
            return current.distance
        }

        for _, delta := range directions {
            nextRow := current.row + delta.row
            nextCol := current.col + delta.col

            next := Pair{nextRow, nextCol}

            if !reachable[next] {
                continue
            }

            if bfsVisited[next] {
                continue
            }

            bfsVisited[next] = true

            queue = append(queue, State{
                row:      nextRow,
                col:      nextCol,
                distance: current.distance + 1,
            })
        }
    }

    return -1
}

The Go implementation follows the same overall strategy as the Python version.

Since Go does not have tuples, custom structs Pair and State are used for coordinates and BFS states.

Maps with Pair keys act like Python hash sets. BFS is implemented using a slice as a queue, removing elements from the front as traversal proceeds.

Go uses byte instead of string for direction characters because the API signature expects byte values.

Worked Examples

Example 1

grid = [
  [1, 2],
  [-1, 0]
]

Virtual coordinate mapping:

(0,0) = start
(-1,0) = empty
(-1,1) = target

DFS Exploration

Step Position Action
1 (0,0) Start DFS
2 (-1,0) Move Up
3 (-1,1) Move Right, found target
4 (-1,0) Backtrack Left
5 (0,0) Backtrack Down

Reachable cells:

{
    (0,0),
    (-1,0),
    (-1,1)
}

Target coordinate:

(-1,1)

BFS Traversal

Queue Current Distance
[(0,0,0)] (0,0) 0
[(-1,0,1)] (-1,0) 1
[(-1,1,2)] (-1,1) 2

Answer:

2

Example 2

grid = [
  [0,0,-1],
  [1,1,1],
  [2,0,0]
]

The robot explores the connected component reachable from the start.

The shortest route becomes:

Start
→ Down
→ Left
→ Left
→ Down

Total distance:

4

Example 3

grid = [
  [-1,0],
  [0,2]
]

The starting cell has no reachable neighbors.

DFS only discovers:

{(0,0)}

The target is never encountered.

Result:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(V + E) DFS explores reachable cells once, BFS traverses the discovered graph once
Space O(V) Visited sets, reachable map, recursion stack, and BFS queue

Here, V is the number of reachable cells and E is the number of edges between reachable neighboring cells.

Because each reachable cell is processed a constant number of times during DFS and BFS, the algorithm is linear in the size of the discovered graph.

Test Cases

# Example 1
assert solution.findShortestPath(master1) == 2  # simple reachable target

# Example 2
assert solution.findShortestPath(master2) == 4  # longer valid path

# Example 3
assert solution.findShortestPath(master3) == -1  # unreachable target

# Target adjacent to start
assert solution.findShortestPath(master4) == 1  # immediate neighbor

# Single narrow corridor
assert solution.findShortestPath(master5) == 7  # linear traversal

# Grid with cycles
assert solution.findShortestPath(master6) == 3  # ensures visited prevents loops

# Large open region
assert solution.findShortestPath(master7) == 12  # stress traversal efficiency

# Dead ends before target
assert solution.findShortestPath(master8) == 5  # DFS must backtrack correctly

# Completely isolated start
assert solution.findShortestPath(master9) == -1  # no reachable cells except start

# Multiple shortest paths
assert solution.findShortestPath(master10) == 6  # BFS should return minimal distance
Test Why
Simple reachable target Validates basic traversal
Longer path Ensures BFS computes true shortest distance
Unreachable target Confirms correct -1 handling
Adjacent target Smallest nonzero answer
Narrow corridor Tests deep recursion
Cyclic graph Prevents infinite revisiting
Large open region Stress tests traversal efficiency
Dead ends Validates DFS backtracking
Isolated start Ensures no invalid movement
Multiple shortest paths Confirms BFS optimality

Edge Cases

One important edge case occurs when the target is unreachable. The DFS exploration may fully traverse the reachable region without ever encountering the target. A buggy implementation might still attempt BFS toward an undefined target coordinate. This implementation avoids that issue by explicitly checking whether the target was discovered before starting BFS.

Another critical edge case involves cycles in the reachable graph. Without a visited set, DFS could repeatedly revisit the same coordinates forever. The implementation stores every explored virtual coordinate in visited, ensuring each reachable cell is processed only once.

Backtracking correctness is another subtle issue. Since the robot physically moves during DFS, recursion alone is not enough to restore state. If the implementation forgets to move back after recursive exploration, future DFS calls operate from the wrong physical position, corrupting the entire traversal. This solution guarantees correctness by always issuing the opposite move immediately after recursive calls return.

A final edge case involves extremely deep reachable regions such as long corridors. DFS recursion depth grows with path length. While the reachable component is bounded by problem constraints, the algorithm still correctly handles these cases because each recursive call explores exactly one new coordinate and then backtracks safely.