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 dequeclass Solution:def minimumSeconds(self, land: List[List[str]]) -> int:# 思路：两次广搜m, n = len(land), len(land[0])# 第一步，从所有"*"的位置（即被淹没的位置）开始进行广搜，使用times1矩阵标记被淹没的时间，不能被淹没的位置标记为inftimes1 = [[inf] * n for _ in range(m)]times2 = [[inf] * n for _ in range(m)]que1 = deque()que2 = deque()dstR, dstC = 0, 0for i in range(m):for j in range(n):if land[i][j] == "*":times1[i][j] = 0que1.append((i, j))elif land[i][j] == 'S':times2[i][j] = 0que2.append((i, j))elif land[i][j] == 'D':dstR, dstC = i, jtime1 = 0while que1:time1 += 1for _ in range(len(que1)):r, c = que1.popleft()for dr, dc in [[-1, 0], [0, -1], [1, 0], [0, 1]]:nr, nc = r + dr, c + dcif 0 <= nr < m and 0 <= nc < n and times1[nr][nc] == inf and land[nr][nc] != 'X' and land[nr][nc] != 'D':que1.append((nr, nc))times1[nr][nc] = time1# print(times1)# 第二步，从"S"的位置开始进行广搜，并记录广搜到各处的时间，并跳过石头处和被淹没处，构建到达各处的时间矩阵times2time2 = 0while que2:time2 += 1for _ in range(len(que2)):r, c = que2.popleft()for dr, dc in [[-1, 0], [0, -1], [1, 0], [0, 1]]:nr, nc = r + dr, c + dcif 0 <= nr < m and 0 <= nc < n and times2[nr][nc] == inf and land[nr][nc] != 'X' and time2 < times1[nr][nc]:que2.append((nr, nc))times2[nr][nc] = time2# print(times2)# 第三步，最终times2["D处位置"]=inf说明不能到达，否则返回所用时间return times2[dstR][dstC] if times2[dstR][dstC] != inf else -1
4.执行结果
