圖論:最接近的迷宮出口 Nearest Exit from Entrance in Maze_Leetcode 1926

Susan Q Yin on Unsplash

題目敘述

題目給定一個二維陣列maze代表迷宮的布局，
其中標記為"."的地方代表可通過，標記為"+"代表牆壁不可通過。

每次移動的時候，可以選擇往上、下、左、右移動一格。

請問從出發點entrance開始走的話，抵達迷宮出口最短距離的步數是多少？

如果無解的話，返回-1。

題目的原文敘述

測試範例

Example 1:

Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Output: 1
Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.

Example 2:

Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
Output: 2
Explanation: There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.

Example 3:

Input: maze = [[".","+"]], entrance = [0,0]
Output: -1
Explanation: There are no exits in this maze.

約束條件

Constraints:

• maze.length == m

迷宮的高為m

• maze[i].length == n

迷宮的寬為n

• 1 <= m, n <= 100

高和寬都會介於1~100之間。

• maze[i][j] is either '.' or '+'.

迷宮陣列內部只會標記為'.'代表可以通過，或者'+'代表式牆壁不可通過。

• entrance.length == 2