## Problem

This is an **interactive problem**.

There is a robot in a hidden grid, and you are trying to get it from its starting cell to the target cell in this grid. The grid is of size `m x n`

, and each cell in the grid is either empty or blocked. It is **guaranteed** that the starting cell and the target cell are different, and neither of them is blocked.

You want to find the minimum distance to the target cell. However, you **do not know** the grid’s dimensions, the starting cell, nor the target cell. You are only allowed to ask queries to the `GridMaster`

object.

The `GridMaster`

class has the following functions:

`boolean canMove(char direction)`

Returns`true`

if the robot can move in that direction. Otherwise, it returns`false`

.`void move(char direction)`

Moves the robot in that direction. If this move would move the robot to a blocked cell or off the grid, the move will be**ignored**, and the robot will remain in the same position.`boolean 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 no valid path between the cells, 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)`

(the starting cell).`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:**

1 | Input: grid = [[1,2],[-1,0]] |

**Example 2:**

1 | Input: grid = [[0,0,-1],[1,1,1],[2,0,0]] |

**Example 3:**

1 | Input: grid = [[-1,0],[0,2]] |

**Constraints:**

`1 <= n, m <= 500`

`m == grid.length`

`n == grid[i].length`

`grid[i][j]`

is either`-1`

,`0`

,`1`

, or`2`

.- There is
**exactly one**`-1`

in`grid`

. - There is
**exactly one**`2`

in`grid`

.

## Analysis

和上面那题一样，这题也是有关hidden grid二题目。总体思路再提一遍：

- 先用DFS把hidden grid构建出来，存储的方法有两种，
`unordered_map`

或者二维矩阵； - 转化为基本的图问题后，再利用BFS或者dijkstra等基本的图算法求解题目。

我们还是先看第二步，题目要求找最短路径，毫无疑问就是BFS了。然后我们来看第一步怎么做，上一道题目我用了`unordered_map`

的方法存储grid，这道题目我就换一种方法，用二维矩阵来存储。这里我们假设起点是`(501, 501)`

，那么总长度就应该是`1001`

，这样才能保证不会越界。其他的就是基本的DFS把每个位置能否移动标记出来即可。

## Solution

无。

## Code

1 | /** |

## Summary

连续两道有关hidden grid的题目，相信大家已经能把这种类型的题目弄清楚了。其本质还是先DFS构造出图，进而把题目转变成正常的图类型的题目来处理。这道题目的分享到这里，感谢你的支持！