1926. Nearest Exit from Entrance in Maze
龙大被困在边板了,总是忍不住偷看边板,龙大想要从边板逃出去他必须要走过一个迷宫
而且走太慢会被边板仔抓回来,所以龙大要走最短的路线逃走,求出龙大逃出边板这个
迷宫最短需要走几步(逃不出去就返回-1)。
+:墙壁不能走
.:道路
Example:
https://assets.leetcode.com/uploads/2021/06/04/nearest1-grid.jpg
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.
思路:
1.一开始用DFS找出口吃了TLE,因为这题是要求最短路径所以用BFS效率比较好,不用
算出所有的路线(BFS只要找到任意一个出口,该出口必定是最短出口)
2.一开始先把入口设定成墙壁(不能从迷宫入口回走,龙大会回到边板)
3.然后从起点的上下左右出发用queue来跑BFS,纪录移动后的座标{X, Y, 距离}
如果遇到边界表示碰到一个出口,如果这个出口不是起点就返回我们已经走的距离。
4.放入Queue的条件是下个点的位置不是墙壁,我们要把每个走过的地方都标记成墙壁
避免回头走。
JavaCode: