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代码
from collections import deque
class Solution:
def minimumSeconds(self, land: List]) -> int:
# 思路：两次广搜
m, n = len(land), len(land)
# 第一步，从所有"*"的位置（即被淹没的位置）开始进行广搜，使用times1矩阵标记被淹没的时间，不能被淹没的位置标记为inf
times1 = [ * n for _ in range(m)]
times2 = [ * n for _ in range(m)]
que1 = deque()
que2 = deque()
dstR, dstC = 0, 0
for i in range(m):
for j in range(n):
if land == "*":
times1 = 0
que1.append((i, j))
elif land == 'S':
times2 = 0
que2.append((i, j))
elif land == 'D':
dstR, dstC = i, j
time1 = 0
while que1:
time1 += 1
for _ in range(len(que1)):
r, c = que1.popleft()
for dr, dc in [[-1, 0], , , ]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and times1 == inf and land != 'X' and land != 'D':
que1.append((nr, nc))
times1 = time1
# print(times1)
# 第二步，从"S"的位置开始进行广搜，并记录广搜到各处的时间，并跳过石头处和被淹没处，构建到达各处的时间矩阵times2
time2 = 0
while que2:
time2 += 1
for _ in range(len(que2)):
r, c = que2.popleft()
for dr, dc in [[-1, 0], , , ]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and times2 == inf and land != 'X' and time2 < times1:
que2.append((nr, nc))
times2 = time2
# print(times2)
# 第三步，最终times2["D处位置"]=inf说明不能到达，否则返回所用时间
return times2 if times2 != inf else -1
4.实行效果
https://i-blog.csdnimg.cn/direct/53b55f4de6444cf4aa8c8ca0b99707a2.png#pic_center
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]