Shortest Path in a Hidden Grid

medium graph bfs dfs grid

Problem

A robot starts at an unknown cell of a hidden grid and you must guide it to a target cell. You cannot see the grid directly; instead a GridMaster interface lets you ask canMove(dir), actually move(dir), and check isTarget(). The grid contains blocked cells you cannot enter. Return the length of the shortest path from the start to the target, or -1 if it is unreachable.

Because you cannot see the layout, the trick is two phases. First DFS: walk the robot everywhere it can go, recording which cells are open and where the target is, building a full map (and backtracking by moving in the opposite direction). Then, on the now-known map, run an ordinary BFS from the start to the target to get the shortest distance.

Input

S O X O
X O X O
O O O O
O X X T

Output6

S is the start, T the target, X blocked. After mapping the grid, BFS finds a 6-step path to T.

hidden grid (rows by ';', cells by space; S start, T target, O open, X blocked)

from collections import deque

def find_shortest_path(master):
    DIRS = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
    OPP = {'U': 'D', 'D': 'U', 'L': 'R', 'R': 'L'}
    grid = {(0, 0): 0}
    target = [None]

    def dfs(r, c):
        if master.isTarget():
            target[0] = (r, c)
        for d, (dr, dc) in DIRS.items():
            nr, nc = r + dr, c + dc
            if master.canMove(d) and (nr, nc) not in grid:
                grid[(nr, nc)] = 0
                master.move(d)
                dfs(nr, nc)
                master.move(OPP[d])

    dfs(0, 0)
    if target[0] is None:
        return -1
    q = deque([((0, 0), 0)])
    seen = {(0, 0)}
    while q:
        (r, c), dist = q.popleft()
        if (r, c) == target[0]:
            return dist
        for dr, dc in DIRS.values():
            nb = (r + dr, c + dc)
            if nb in grid and nb not in seen:
                seen.add(nb)
                q.append((nb, dist + 1))
    return -1

function findShortestPath(master) {
  const DIRS = { U: [-1, 0], D: [1, 0], L: [0, -1], R: [0, 1] };
  const OPP = { U: 'D', D: 'U', L: 'R', R: 'L' };
  const grid = new Set(['0,0']);
  let target = null;
  function dfs(r, c) {
    if (master.isTarget()) target = [r, c];
    for (const d in DIRS) {
      const nr = r + DIRS[d][0], nc = c + DIRS[d][1];
      if (master.canMove(d) && !grid.has(nr + ',' + nc)) {
        grid.add(nr + ',' + nc);
        master.move(d);
        dfs(nr, nc);
        master.move(OPP[d]);
      }
    }
  }
  dfs(0, 0);
  if (!target) return -1;
  const q = [[0, 0, 0]];
  const seen = new Set(['0,0']);
  for (let h = 0; h < q.length; h++) {
    const [r, c, dist] = q[h];
    if (r === target[0] && c === target[1]) return dist;
    for (const d in DIRS) {
      const nr = r + DIRS[d][0], nc = c + DIRS[d][1];
      if (grid.has(nr + ',' + nc) && !seen.has(nr + ',' + nc)) {
        seen.add(nr + ',' + nc);
        q.push([nr, nc, dist + 1]);
      }
    }
  }
  return -1;
}

class Solution {
    int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
    char[] DC = {'U','D','L','R'};
    char[] OPP = {'D','U','R','L'};
    Set<Long> grid = new HashSet<>();
    long target = -1;
    long key(int r, int c) { return (long) r * 1000 + c; }

    void dfs(GridMaster m, int r, int c) {
        if (m.isTarget()) target = key(r, c);
        for (int i = 0; i < 4; i++) {
            int nr = r + DIRS[i][0], nc = c + DIRS[i][1];
            if (m.canMove(DC[i]) && !grid.contains(key(nr, nc))) {
                grid.add(key(nr, nc));
                m.move(DC[i]);
                dfs(m, nr, nc);
                m.move(OPP[i]);
            }
        }
    }

    public int findShortestPath(GridMaster master) {
        grid.add(key(0, 0));
        dfs(master, 0, 0);
        if (target == -1) return -1;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0, 0});
        Set<Long> seen = new HashSet<>(); seen.add(key(0, 0));
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (key(cur[0], cur[1]) == target) return cur[2];
            for (int[] dir : DIRS) {
                int nr = cur[0] + dir[0], nc = cur[1] + dir[1];
                if (grid.contains(key(nr, nc)) && !seen.contains(key(nr, nc))) {
                    seen.add(key(nr, nc));
                    q.offer(new int[]{nr, nc, cur[2] + 1});
                }
            }
        }
        return -1;
    }
}

class Solution {
    int DIRS[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    char DC[4] = {'U','D','L','R'};
    char OPP[4] = {'D','U','R','L'};
    set<pair<int,int>> grid;
    pair<int,int> target = {-1000, -1000};
    void dfs(GridMaster& m, int r, int c) {
        if (m.isTarget()) target = {r, c};
        for (int i = 0; i < 4; i++) {
            int nr = r + DIRS[i][0], nc = c + DIRS[i][1];
            if (m.canMove(DC[i]) && !grid.count({nr, nc})) {
                grid.insert({nr, nc});
                m.move(DC[i]);
                dfs(m, nr, nc);
                m.move(OPP[i]);
            }
        }
    }
public:
    int findShortestPath(GridMaster& master) {
        grid.insert({0, 0});
        dfs(master, 0, 0);
        if (target.first == -1000) return -1;
        queue<array<int,3>> q; q.push({0, 0, 0});
        set<pair<int,int>> seen; seen.insert({0, 0});
        while (!q.empty()) {
            auto [r, c, d] = q.front(); q.pop();
            if (make_pair(r, c) == target) return d;
            for (auto& dir : DIRS) {
                int nr = r + dir[0], nc = c + dir[1];
                if (grid.count({nr, nc}) && !seen.count({nr, nc})) {
                    seen.insert({nr, nc});
                    q.push({nr, nc, d + 1});
                }
            }
        }
        return -1;
    }
};

Explanation

The catch is that you start blind — you can only feel your way around through the robot. So the algorithm splits into explore first, then solve.

Phase 1 (DFS mapping). Treating the start as coordinate (0,0), we try each direction. If canMove says a neighbour is open and we have not recorded it yet, we physically move the robot there, mark the cell as open, record whether it is the target, recurse, and then move back the opposite way to restore the robot's position. After the DFS unwinds, we hold a complete map of every reachable open cell.

Phase 2 (BFS shortest path). Now the grid is fully known, so the hidden-interface difficulty is gone. We run a plain breadth-first search from (0,0) over the discovered cells, expanding ring by ring until we pop the target cell, whose recorded distance is the shortest path length.

If the DFS never lands on the target, it is unreachable and we return -1. Note the BFS must run on the built map, not on the robot — replaying robot moves would not give shortest paths.

Worked example: the DFS maps the open corridor winding down to T; BFS then measures the route (0,0)→(0,1)→(1,1)→(2,1)→(2,2)→(2,3)→(3,3), a length of 6.

Time: O(R · C) Space: O(R · C)