shortest Path in Hidden Grid [Robot]

1778.Shortest Path in a Hidden Grid

Simulation

Graph

Problem Statement:

There is a robot in a hidden grid, and you are tasked with finding the shortest path from the starting cell to the target cell. The grid has unknown dimensions, and you can only interact with it through a GridMaster object with the following methods:

• boolean canMove(char direction): Returns true if the robot can move in the specified direction.
• void move(char direction): Moves the robot in the specified direction if possible.
• boolean isTarget(): Returns true if the robot is on the target cell.

Your goal is to return the shortest distance from the starting cell to the target cell. If no valid path exists, return -1.

Algorithm:

1. Perform a **DFS traversal** starting from the initial cell to explore the grid:
   • Mark cells as visited to avoid revisiting them.
   • Simulate movement using the GridMaster API.
2. During the DFS, construct a virtual graph representation of the accessible cells.
3. After the DFS traversal:
   • Use **Breadth-First Search (BFS)** on the constructed graph to compute the shortest path from the start to the target.
4. If the target is unreachable, return -1.

Complexity:

Time: O(m × n), where m and n are the dimensions of the grid.
Space: O(m × n) for the graph representation.

Java Implementation:

class Solution {
    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static final char[] MOVE = {'U', 'D', 'L', 'R'};
    private static final char[] BACK = {'D', 'U', 'R', 'L'};

    public int findShortestPath(GridMaster master) {
        Map grid = new HashMap<>();
        grid.put("0,0", 0);
        if (!dfs(master, grid, 0, 0)) return -1;

        Queue queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int d = 0; d < 4; d++) {
                int nx = cell[0] + DIRS[d][0], ny = cell[1] + DIRS[d][1];
                if (grid.containsKey(nx + "," + ny) && grid.get(nx + "," + ny) > grid.get(cell[0] + "," + cell[1]) + 1) {
                    queue.add(new int[]{nx, ny});
                    grid.put(nx + "," + ny, grid.get(cell[0] + "," + cell[1]) + 1);
                }
            }
        }
        return grid.getOrDefault("target", -1);
    }

    private boolean dfs(GridMaster master, Map grid, int x, int y) {
        if (master.isTarget()) {
            grid.put("target", grid.get(x + "," + y));
            return true;
        }
        for (int d = 0; d < 4; d++) {
            int nx = x + DIRS[d][0], ny = y + DIRS[d][1];
            if (!grid.containsKey(nx + "," + ny) && master.canMove(MOVE[d])) {
                grid.put(nx + "," + ny, grid.get(x + "," + y) + 1);
                master.move(MOVE[d]);
                if (dfs(master, grid, nx, ny)) return true;
                master.move(BACK[d]);
            }
        }
        return false;
    }
}

Python Implementation:

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
MOVE = ['U', 'D', 'L', 'R']
BACK = ['D', 'U', 'R', 'L']

def findShortestPath(master):
    grid = {(0, 0): 0}
    if not dfs(master, grid, 0, 0):
        return -1

    queue = deque([(0, 0)])
    while queue:
        x, y = queue.popleft()
        for dx, dy in DIRS:
            nx, ny = x + dx, y + dy
            if (nx, ny) in grid and grid[(nx, ny)] > grid[(x, y)] + 1:
                queue.append((nx, ny))
                grid[(nx, ny)] = grid[(x, y)] + 1
    return grid.get("target", -1)

def dfs(master, grid, x, y):
    if master.isTarget():
        grid["target"] = grid[(x, y)]
        return True
    for i, (dx, dy) in enumerate(DIRS):
        nx, ny = x + dx, y + dy
        if (nx, ny) not in grid and master.canMove(MOVE[i]):
            grid[(nx, ny)] = grid[(x, y)] + 1
            master.move(MOVE[i])
            if dfs(master, grid, nx, ny):
                return True
            master.move(BACK[i])
    return False

C++ Implementation:

class Solution {
public:
    const vector> DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    const vector MOVE = {'U', 'D', 'L', 'R'};
    const vector BACK = {'D', 'U', 'R', 'L'};

    int findShortestPath(GridMaster &master) {
        map, int> grid;
        grid[{0, 0}] = 0;
        if (!dfs(master, grid, 0, 0)) return -1;

        queue> q;
        q.push({0, 0});
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (auto [dx, dy] : DIRS) {
                int nx = x + dx, ny = y + dy;
                if (grid.count({nx, ny}) && grid[{nx, ny}] > grid[{x, y}] + 1) {
                    q.push({nx, ny});
                    grid[{nx, ny}] = grid[{x, y}] + 1;
                }
            }
        }
        return grid.count({"target"}) ? grid[{"target"}] : -1;
    }

    bool dfs(GridMaster &master, map, int> &grid, int x, int y) {
        if (master.isTarget()) {
            grid[{"target"}] = grid[{x, y}];
            return true;
        }
        for (int i = 0; i < 4; ++i) {
            int nx = x + DIRS[i].first, ny = y + DIRS[i].second;
            if (!grid.count({nx, ny}) && master.canMove(MOVE[i])) {
                grid[{nx, ny}] = grid[{x, y}] + 1;
                master.move(MOVE[i]);
                if (dfs(master, grid, nx, ny)) return true;
                master.move(BACK[i]);
            }
        }
        return false;
    }
};
                

Tal Nabulsi