Leetcode 2814. 避免淹死并到达目的地的最短时间【Plus题】 ...

1.标题基本信息

1.1.标题形貌

现给定一个 n * m 的索引从 0 开始的二维字符串网格 land，目前你站在为 “S” 的单元格上，你需要到达为 “D” 的单元格。在这片地区上还有另外三种类型的单元格：
“.”：这些单元格是空的。
“X”：这些单元格是石头。
“*”：这些单元格被沉没了。
每秒钟，你可以移动到与当前单元格共享边的单元格（如果它存在）。别的，每秒钟，与被沉没的单元格共享边的每个 空单元格 也会被沉没。
在你的旅程中，有两个需要留意的题目：
你不能踩在石头单元格上。
你不能踩在被沉没的单元格上，由于你会淹死（同时，你也不能踩在在你踩上时会被沉没的单元格上）。
返回从起始位置到达目的位置所需的 最小 时间（以秒为单元），如果不大概到达目的位置，则返回 -1。
留意，目的位置永世不会被沉没。
1.2.标题地点

https://leetcode.cn/problems/minimum-time-takes-to-reach-destination-without-drowning/description/
2.解题方法

2.1.解题思路

两次广度优先搜索
2.2.解题步骤

第一步，从所有”*”的位置（即被沉没的位置）开始进行广搜，利用times1矩阵标记被沉没的时间，不能被沉没的位置标记为inf
第二步，从”S”的位置开始进行广搜，并记录广搜到各处的时间，并跳过石头处和被沉没处，构建到达各处的时间矩阵times2
第三步，终极times2[“D处位置”]=inf阐明不能到达，否则返回所用时间
3.解题代码

Python代码

1. from collections import deque
3. class Solution:
4.     def minimumSeconds(self, land: List[List[str]]) -> int:
5.         # 思路：两次广搜
6.         m, n = len(land), len(land[0])
7.         # 第一步，从所有"*"的位置（即被淹没的位置）开始进行广搜，使用times1矩阵标记被淹没的时间，不能被淹没的位置标记为inf
8.         times1 = [[inf] * n for _ in range(m)]
9.         times2 = [[inf] * n for _ in range(m)]
10.         que1 = deque()
11.         que2 = deque()
12.         dstR, dstC = 0, 0
13.         for i in range(m):
14.             for j in range(n):
15.                 if land[i][j] == "*":
16.                     times1[i][j] = 0
17.                     que1.append((i, j))
18.                 elif land[i][j] == 'S':
19.                     times2[i][j] = 0
20.                     que2.append((i, j))
21.                 elif land[i][j] == 'D':
22.                     dstR, dstC = i, j
23.         time1 = 0
24.         while que1:
25.             time1 += 1
26.             for _ in range(len(que1)):
27.                 r, c = que1.popleft()
28.                 for dr, dc in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
29.                     nr, nc = r + dr, c + dc
30.                     if 0 <= nr < m and 0 <= nc < n and times1[nr][nc] == inf and land[nr][nc] != 'X' and land[nr][nc] != 'D':
31.                         que1.append((nr, nc))
32.                         times1[nr][nc] = time1
33.         # print(times1)
34.         # 第二步，从"S"的位置开始进行广搜，并记录广搜到各处的时间，并跳过石头处和被淹没处，构建到达各处的时间矩阵times2
35.         time2 = 0
36.         while que2:
37.             time2 += 1
38.             for _ in range(len(que2)):
39.                 r, c = que2.popleft()
40.                 for dr, dc in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
41.                     nr, nc = r + dr, c + dc
42.                     if 0 <= nr < m and 0 <= nc < n and times2[nr][nc] == inf and land[nr][nc] != 'X' and time2 < times1[nr][nc]:
43.                         que2.append((nr, nc))
44.                         times2[nr][nc] = time2
45.         # print(times2)
46.         # 第三步，最终times2["D处位置"]=inf说明不能到达，否则返回所用时间
47.         return times2[dstR][dstC] if times2[dstR][dstC] != inf else -1

复制代码

4.实行效果

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。