Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2022-11-21 23:21:37
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:
作者: EMANON231 (荷莉叶特)   2022-11-21 23:23:00
靠北
作者: v03516020 (露露贝尔)   2022-11-21 23:25:00
@d*******
作者: sustainer123 (caster)   2022-11-21 23:25:00
大师
作者: SecondRun (雨夜琴声)   2022-11-21 23:27:00
BFS
作者: pandix (面包屌)   2022-11-21 23:41:00
大师
作者: NTHUlagka (拉卡)   2022-11-22 01:30:00
大师
作者: dannyko (dannyko)   2022-11-22 03:04:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com