---
description: DFS+BFS
---

# LeetCode 1778. Shortest Path in a Hidden Grid



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:

[English Version in Youtube](https://youtu.be/P8H-oxAQAuY)

[中文版解答Youtube Link](https://youtu.be/tfNTJtdOW6c)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1i54y1a74m/)

```
/**
 * // 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 {
public:
    // 0 is blocked, 1 is empty, 2 is target
    void ConstructGrid(vector<vector<int>>& grid, GridMaster &master, int row, int col, const map<char, pair<int, int>>& directions) {
        grid[row][col] = 1;
        if (master.isTarget()) {
            grid[row][col] = 2;
        }
        
        for (const auto& direction : directions) {
            int new_row = row + direction.second.first;
            int new_col = col + direction.second.second;
            if (grid[new_row][new_col] != -1) {
                continue;
            }
            if (master.canMove(direction.first)) {
                master.move(direction.first);
                ConstructGrid(grid, master, new_row, new_col, directions);
                if (direction.first == 'U') master.move('D');
                else if (direction.first == 'D') master.move('U');
                else if (direction.first == 'L') master.move('R');
                else master.move('L');
            } else {
                grid[new_row][new_col] = 0;
            }
        }
    }
    
    int findShortestPath(GridMaster &master) {
        map<char, pair<int, int>> directions = {
            {'U', {0, 1}},
            {'D', {0, -1}},
            {'L', {-1, 0}},
            {'R', {1, 0}},
        };
        
        vector<vector<int>> grid(1001, vector<int>(1001, -1));
        ConstructGrid(grid, master, 501, 501, directions);
        
        queue<pair<int, int>> myqueue;
        myqueue.push({501, 501});
        grid[501][501] = 0;
        
        int distance = 1;
        while (!myqueue.empty()) {
            int queue_size = myqueue.size();
            for (int k = 0; k < queue_size; k++) {
                pair<int, int> cur = myqueue.front();
                myqueue.pop();
                
                for (const auto& direction : directions) {
                    int new_row = cur.first + direction.second.first;
                    int new_col = cur.second + direction.second.second;
                    if (grid[new_row][new_col] == 2) {
                        return distance;
                    }
                    if (grid[new_row][new_col] <= 0) {
                        continue;
                    }
                    // Mark as 'visited'.
                    grid[new_row][new_col] = 0;
                    myqueue.push({new_row, new_col});
                }
            }
            
            distance++;
        }
        
        return -1;
    }
};
```
