Formatted question description: https://leetcode.ca/all/1778.html

1778. Shortest Path in a Hidden Grid

Level

Medium

Description

This is an interactive problem.

You are given a robot in a hidden grid, and it wants to go to a target cell in this grid. The grid is of size m x n, and each cell in the grid can be empty or blocked. It is guaranteed that the start point and the robot’s destination are different, and neither of them is blocked.

You want to find the robot’s minimum distance to the target cell. However, you do not know the grid’s dimensions, or the starting point of the robot, or its target destination. You are only allowed to ask queries to your GridMaster object.

You are given a class GridMaster which you can call the following functions from:

boolean GridMaster.canMove(char direction) returns true if the robot can move in that direction. Otherwise, it returns false.
void GridMaster.move(char direction) moves the robot in that direction. If this move would move the robot to a blocked cell or off the grid, it will be ignored, and the robot would remain in the same position.
boolean GridMaster.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 a path between them. Otherwise, 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).
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 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 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:

m == grid.length
n == grid[i].length
1 <= n, m <= 500
grid[i][j] is either -1, 0, 1, or 2.
There is exactly one -1 in grid.
There is exactly one 2 in grid.

Solution

To find the shortest path, a typical approach is breadth first search. However, in this problem, only an instance of GridMaster is available, and the instance cannot be used directly for breadth first search. However, by using the GridMaster instance, the grid can be found out.

Since the maximum number of rows and columns do not exceed 500, create a 2D array grid with 1000 rows and 1000 columns and let (500, 500) be the start position of the robot. Do depth first search starting from the original cell of the robot to figure out all values in grid and determine whether the target cell can be reached. If the target cell cannot be reached, return -1. Otherwise, do breadth first search starting from the original cell to find the shortest path to reach the target cell.

/**
 * // This is the GridMaster's API interface.
 * // You should not implement it, or speculate about its implementation
 * class GridMaster {
 *     boolean canMove(char direction);
 *     void move(char direction);
 *     boolean isTarget();
 * }
 */

class Solution {
    static final int MAX = 500;
    char[] directionsChar = {'U', 'L', 'D', 'R'};
    int[][] directionsArr = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };
    boolean flag = false;

    public int findShortestPath(GridMaster master) {
        Set<String> visited1 = new HashSet<String>();
        int[][] grid = new int[MAX * 2][MAX * 2];
        grid[MAX][MAX] = -1;
        depthFirstSearch(MAX, MAX, visited1, grid, master);
        if (!flag)
            return -1;
        int distance = 0;
        boolean[][] visited2 = new boolean[MAX * 2][MAX * 2];
        visited2[MAX][MAX] = true;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{MAX, MAX});
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                int row = cell[0], column = cell[1];
                if (grid[row][column] == 2)
                    return distance;
                for (int[] directionArr : directionsArr) {
                    int newRow = row + directionArr[0], newColumn = column + directionArr[1];
                    if (!visited2[newRow][newColumn] && grid[newRow][newColumn] != 0) {
                        visited2[newRow][newColumn] = true;
                        queue.offer(new int[]{newRow, newColumn});
                    }
                }
            }
            distance++;
        }
        return -1;
    }

    public void depthFirstSearch(int row, int column, Set<String> visited, int[][] grid, GridMaster master) {
        grid[row][column] = 1;
        if (master.isTarget()) {
            grid[row][column] = 2;
            flag = true;
        }
        for (int i = 0; i < 4; i++) {
            char directionChar = directionsChar[i];
            char oppositeDirectionChar = directionsChar[(i + 2) % 4];
            int[] directionArr = directionsArr[i];
            int newRow = row + directionArr[0], newColumn = column + directionArr[1];
            String newStr = Arrays.toString(new int[]{newRow, newColumn});
            if (!visited.contains(newStr) && master.canMove(directionChar)) {
                visited.add(newStr);
                master.move(directionChar);
                depthFirstSearch(newRow, newColumn, visited, grid, master);
                master.move(oppositeDirectionChar);
            }
        }
    }
}

############

/**
 * // This is the GridMaster's API interface.
 * // You should not implement it, or speculate about its implementation
 * class GridMaster {
 *     boolean canMove(char direction);
 *     void move(char direction);
 *     boolean isTarget();
 * }
 */

class Solution {
    private static final char[] dir = {'U', 'R', 'D', 'L'};
    private static final char[] ndir = {'D', 'L', 'U', 'R'};
    private static final int[] dirs = {-1, 0, 1, 0, -1};
    private static final int N = 1010;
    private Set<Integer> s;
    private int[] target;

    public int findShortestPath(GridMaster master) {
        target = null;
        s = new HashSet<>();
        s.add(0);
        dfs(0, 0, master);
        if (target == null) {
            return -1;
        }
        s.remove(0);
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {0, 0});
        int ans = -1;
        while (!q.isEmpty()) {
            ++ans;
            for (int n = q.size(); n > 0; --n) {
                int[] p = q.poll();
                int i = p[0], j = p[1];
                if (target[0] == i && target[1] == j) {
                    return ans;
                }
                for (int k = 0; k < 4; ++k) {
                    int x = i + dirs[k], y = j + dirs[k + 1];
                    if (s.contains(x * N + y)) {
                        s.remove(x * N + y);
                        q.offer(new int[] {x, y});
                    }
                }
            }
        }
        return -1;
    }

    private void dfs(int i, int j, GridMaster master) {
        if (master.isTarget()) {
            target = new int[] {i, j};
        }
        for (int k = 0; k < 4; ++k) {
            char d = dir[k], nd = ndir[k];
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (master.canMove(d) && !s.contains(x * N + y)) {
                s.add(x * N + y);
                master.move(d);
                dfs(x, y, master);
                master.move(nd);
            }
        }
    }
}

# """
# 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:
#
#
#    def move(self, direction: str) -> bool:
#
#
#    def isTarget(self) -> None:
#
#


class Solution(object):
    def findShortestPath(self, master: 'GridMaster') -> int:
        def dfs(i, j):
            nonlocal target
            if master.isTarget():
                target = (i, j)
            for dir, ndir, a, b in dirs:
                x, y = i + a, j + b
                if master.canMove(dir) and (x, y) not in s:
                    s.add((x, y))
                    master.move(dir)
                    dfs(x, y)
                    master.move(ndir)

        target = None
        s = set()
        dirs = [
            ['U', 'D', -1, 0],
            ['D', 'U', 1, 0],
            ['L', 'R', 0, -1],
            ['R', 'L', 0, 1],
        ]
        dfs(0, 0)
        if target is None:
            return -1
        s.remove((0, 0))
        q = deque([(0, 0)])
        ans = -1
        while q:
            ans += 1
            for _ in range(len(q)):
                i, j = q.popleft()
                if (i, j) == target:
                    return ans
                for _, _, a, b in dirs:
                    x, y = i + a, j + b
                    if (x, y) in s:
                        s.remove((x, y))
                        q.append((x, y))
        return -1

/**
 * // This is the GridMaster's API interface.
 * // You should not implement it, or speculate about its implementation
 * class GridMaster {
 *   public:
 *     bool canMove(char direction);
 *     void move(char direction);
 *     boolean isTarget();
 * };
 */

class Solution {
private:
    const int n = 2010;
    int dirs[5] = {-1, 0, 1, 0, -1};
    string s = "URDL";
    int target;
    unordered_set<int> vis;

public:
    int findShortestPath(GridMaster& master) {
        target = n * n;
        vis.insert(0);
        dfs(0, 0, master);
        if (target == n * n) {
            return -1;
        }
        vis.erase(0);
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        for (int ans = 0; q.size(); ++ans) {
            for (int m = q.size(); m; --m) {
                auto [i, j] = q.front();
                q.pop();
                if (i * n + j == target) {
                    return ans;
                }
                for (int k = 0; k < 4; ++k) {
                    int x = i + dirs[k], y = j + dirs[k + 1];
                    if (vis.count(x * n + y)) {
                        vis.erase(x * n + y);
                        q.emplace(x, y);
                    }
                }
            }
        }
        return -1;
    }

    void dfs(int i, int j, GridMaster& master) {
        if (master.isTarget()) {
            target = i * n + j;
        }
        for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (master.canMove(s[k]) && !vis.count(x * n + y)) {
                vis.insert(x * n + y);
                master.move(s[k]);
                dfs(x, y, master);
                master.move(s[(k + 2) % 4]);
            }
        }
    }
};

1778 - Shortest Path in a Hidden Grid

1778. Shortest Path in a Hidden Grid

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1778. Shortest Path in a Hidden Grid

Level

Description

Solution

All Problems

All Solutions