1778. Shortest Path in a Hidden Grid - Leetcode Solution

Code Implementation

# This code assumes the existence of the GridMaster API as per Leetcode's problem statement.
# The GridMaster API provides the following methods:
# - canMove(direction): returns True if you can move in the given direction ('U','D','L','R')
# - move(direction): moves in the given direction. Returns True if you reach the target cell.
# - isTarget(): returns True if the current cell is the target.

# Directions mapping for convenience
DIRS = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
REVERSE = {'U': 'D', 'D': 'U', 'L': 'R', 'R': 'L'}

class Solution:
    def findShortestPath(self, master: 'GridMaster') -> int:
        from collections import deque

        # First, discover the grid using DFS
        N = 1001  # Arbitrary large enough grid size to avoid negative indexes
        OFFSET = N // 2
        grid = {}
        target = None

        def dfs(x, y):
            nonlocal target
            if master.isTarget():
                target = (x, y)
            grid[(x, y)] = True
            for d in DIRS:
                nx, ny = x + DIRS[d][0], y + DIRS[d][1]
                if (nx, ny) not in grid and master.canMove(d):
                    master.move(d)
                    dfs(nx, ny)
                    master.move(REVERSE[d])  # Backtrack

        dfs(OFFSET, OFFSET)

        # Now, do BFS to find shortest path from start to target
        if not target:
            return -1
        queue = deque()
        queue.append((OFFSET, OFFSET, 0))
        visited = set()
        visited.add((OFFSET, OFFSET))
        while queue:
            x, y, dist = queue.popleft()
            if (x, y) == target:
                return dist
            for d in DIRS:
                nx, ny = x + DIRS[d][0], y + DIRS[d][1]
                if (nx, ny) in grid and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny, dist + 1))
        return -1

// Directions and their corresponding moves
const int N = 1001;
const int OFFSET = N / 2;
const vector<char> DIRS = {'U', 'D', 'L', 'R'};
const vector<int> dx = {-1, 1, 0, 0};
const vector<int> dy = {0, 0, -1, 1};
unordered_map<char, char> REVERSE = {{'U','D'}, {'D','U'}, {'L','R'}, {'R','L'}};

class Solution {
public:
    int findShortestPath(GridMaster &master) {
        unordered_map<int, unordered_map<int, bool>> grid;
        pair<int,int> target = {-1, -1};

        function<void(int,int)> dfs = [&](int x, int y) {
            if (master.isTarget()) target = {x, y};
            grid[x][y] = true;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                char d = DIRS[i];
                if (!grid[nx][ny] && master.canMove(d)) {
                    master.move(d);
                    dfs(nx, ny);
                    master.move(REVERSE[d]);
                }
            }
        };

        dfs(OFFSET, OFFSET);

        if (target.first == -1) return -1;

        queue<tuple<int,int,int>> q;
        q.push({OFFSET, OFFSET, 0});
        unordered_set<long long> visited;
        visited.insert((long long)OFFSET*N + OFFSET);

        while (!q.empty()) {
            auto [x, y, dist] = q.front(); q.pop();
            if (x == target.first && y == target.second) return dist;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (grid[nx][ny] && !visited.count((long long)nx*N + ny)) {
                    visited.insert((long long)nx*N + ny);
                    q.push({nx, ny, dist + 1});
                }
            }
        }
        return -1;
    }
};

class Solution {
    static final int N = 1001;
    static final int OFFSET = N / 2;
    static final char[] DIRS = {'U', 'D', 'L', 'R'};
    static final int[] dx = {-1, 1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};
    static final Map<Character, Character> REVERSE = Map.of('U','D', 'D','U', 'L','R', 'R','L');

    public int findShortestPath(GridMaster master) {
        Map<Integer, Set<Integer>> grid = new HashMap<>();
        int[] target = new int[]{-1, -1};

        dfs(master, OFFSET, OFFSET, grid, target);

        if (target[0] == -1) return -1;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{OFFSET, OFFSET, 0});
        Set<Long> visited = new HashSet<>();
        visited.add((long)OFFSET * N + OFFSET);

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0], y = curr[1], dist = curr[2];
            if (x == target[0] && y == target[1]) return dist;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (grid.containsKey(nx) && grid.get(nx).contains(ny)) {
                    long key = (long)nx * N + ny;
                    if (!visited.contains(key)) {
                        visited.add(key);
                        queue.offer(new int[]{nx, ny, dist + 1});
                    }
                }
            }
        }
        return -1;
    }

    private void dfs(GridMaster master, int x, int y, Map<Integer, Set<Integer>> grid, int[] target) {
        if (master.isTarget()) {
            target[0] = x; target[1] = y;
        }
        grid.computeIfAbsent(x, k -> new HashSet<>()).add(y);
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!grid.containsKey(nx) || !grid.get(nx).contains(ny)) {
                if (master.canMove(DIRS[i])) {
                    master.move(DIRS[i]);
                    dfs(master, nx, ny, grid, target);
                    master.move(REVERSE.get(DIRS[i]));
                }
            }
        }
    }
}

const DIRS = {'U': [-1, 0], 'D': [1, 0], 'L': [0, -1], 'R': [0, 1]};
const REVERSE = {'U': 'D', 'D': 'U', 'L': 'R', 'R': 'L'};

var findShortestPath = function(master) {
    const N = 1001;
    const OFFSET = Math.floor(N / 2);
    const grid = new Map();
    let target = null;

    function setGrid(x, y) {
        if (!grid.has(x)) grid.set(x, new Set());
        grid.get(x).add(y);
    }
    function hasGrid(x, y) {
        return grid.has(x) && grid.get(x).has(y);
    }

    function dfs(x, y) {
        if (master.isTarget()) target = [x, y];
        setGrid(x, y);
        for (let d in DIRS) {
            const [dx, dy] = DIRS[d];
            const nx = x + dx, ny = y + dy;
            if (!hasGrid(nx, ny) && master.canMove(d)) {
                master.move(d);
                dfs(nx, ny);
                master.move(REVERSE[d]);
            }
        }
    }

    dfs(OFFSET, OFFSET);

    if (!target) return -1;
    const queue = [[OFFSET, OFFSET, 0]];
    const visited = new Set();
    visited.add(OFFSET + ',' + OFFSET);

    while (queue.length > 0) {
        const [x, y, dist] = queue.shift();
        if (x === target[0] && y === target[1]) return dist;
        for (let d in DIRS) {
            const [dx, dy] = DIRS[d];
            const nx = x + dx, ny = y + dy;
            if (hasGrid(nx, ny) && !visited.has(nx + ',' + ny)) {
                visited.add(nx + ',' + ny);
                queue.push([nx, ny, dist + 1]);
            }
        }
    }
    return -1;
};

Problem Description

The "Shortest Path in a Hidden Grid" problem presents a grid where some cells are blocked and others are open, but you do not know the layout in advance. You start at a certain cell, and only by moving can you discover which neighboring cells are accessible. Your task is to find the minimum number of moves required to reach the target cell, using only the provided GridMaster API:

canMove(direction): Check if you can move in a given direction ('U', 'D', 'L', 'R').
move(direction): Move in a direction. Returns true if you reach the target.
isTarget(): Returns true if the current cell is the target.

Key constraints:

You do not know the grid's boundaries or the position of the target.
You must not revisit cells unnecessarily.
There is guaranteed to be at most one valid path to the target.
Blocked cells cannot be traversed.

Thought Process

At first glance, this problem seems suited for a classic shortest-path search like BFS. However, the twist is that the grid is "hidden": you can only discover cells by moving, and you don't know the size or shape of the grid up front. This means you cannot directly apply BFS from the start.

The brute-force approach would be to try all possible move sequences, but this is not practical due to possible grid size and blocked cells. Instead, we need a way to systematically explore all reachable cells, record their connections, and then find the shortest path to the target.

The main insight is to use DFS to fully explore and map out the accessible part of the grid, then use BFS on this mapped graph to compute the shortest path.

Solution Approach

Step 1: Discover the Grid with DFS
- Start from the initial position and recursively explore each direction ('U', 'D', 'L', 'R').
- For each move, check if you can move with canMove. If yes, move and mark the new cell as visited.
- Backtrack after exploring each path to restore the master's position.
- While exploring, record the coordinates of each accessible cell in a map or set. Use a large enough coordinate offset to avoid negative indexes.
- If you reach the target (using isTarget()), record its coordinates.
Step 2: Compute Shortest Path with BFS
- Once the grid is mapped, use BFS starting from the initial position to the target position.
- Each cell is a node; adjacent open cells are connected.
- Keep a visited set to avoid revisiting cells.
- Return the length of the shortest path when the target is reached, or -1 if unreachable.
Design Choices:
- DFS is used for exploration because it fits well with the backtracking needed to keep the GridMaster’s internal position consistent.
- BFS is used for shortest path because it guarantees minimal steps in an unweighted graph.
- A coordinate offset is used to handle unknown negative positions.

Example Walkthrough

Suppose the hidden grid looks like this (where S is the start, T is the target, # is blocked, and . is open):

    . . . #
    S # . T
    . . . #
    # # . .

DFS Exploration:
- Start at S. Try moving in all directions. For each valid move, mark the cell as open and recursively explore further.
- Blocked cells are skipped. Each time you move, you backtrack to the previous position after exploring a path.
- When you reach T, record its coordinates.
- After DFS, you have a map of all reachable open cells and the position of the target.
BFS Shortest Path:
- Start BFS from S's coordinates. At each step, move to adjacent open cells not yet visited.
- Continue until you reach T. The number of steps taken is the shortest path length.
- In this example, the shortest path may be: S → right → down → right → up → right → T (5 steps).

Time and Space Complexity

Brute-force:
- Time: Exponential in the number of cells, since every possible path is explored.
- Space: Proportional to the depth of the recursion stack and the number of cells visited.
Optimized Approach (DFS + BFS):
- Time: O(N), where N is the number of accessible cells. Each cell is visited at most once during DFS and once during BFS.
- Space: O(N), for storing the grid map and the BFS queue.
The approach is efficient because it only explores reachable cells and avoids redundant revisits.

Summary

The "Shortest Path in a Hidden Grid" problem cleverly combines exploration and pathfinding in an unknown environment. By first mapping the accessible grid using DFS (with careful backtracking) and then applying BFS for the shortest path, we efficiently solve the problem without unnecessary computation. The solution is elegant because it leverages the strengths of both DFS (for exploration) and BFS (for shortest path), and demonstrates how to adapt classic algorithms to work with a "hidden" or dynamically revealed structure.

AlgoMap.io

Want Help Cracking FAANG?