2814：避免淹死并到达目的地的最短时间（★★）

Ian

2023-08-07 约 877 字预计阅读 2 分钟次阅读

力扣第 2814 题

题目

现给定一个 n * m 的索引从 0 开始的二维字符串网格 land，目前你站在为 "S" 的单元格上，你需要到达为 "D" 的单元格。在这片区域上还有另外三种类型的单元格：

"."：这些单元格是空的。
"X"：这些单元格是石头。
"*"：这些单元格被淹没了。

每秒钟，你可以移动到与当前单元格共享边的单元格（如果它存在）。此外，每秒钟，与被淹没的单元格共享边的每个 空单元格 也会被淹没。

在你的旅程中，有两个需要注意的问题：

你不能踩在石头单元格上。
你不能踩在被淹没的单元格上，因为你会淹死（同时，你也不能踩在在你踩上时会被淹没的单元格上）。

返回从起始位置到达目标位置所需的最小时间（以秒为单位），如果不可能达到目标位置，则返回 -1。

注意，目标位置永远不会被淹没。

示例 1：

输入：land = [["D",".","*"],[".",".","."],[".","S","."]]
输出：3
解释：下面的图片逐秒模拟了土地的变化。蓝色的单元格被淹没，灰色的单元格是石头。
图片（0）显示了初始状态，图片（3）显示了当我们到达目标时的最终状态。正如你所看到的，我们需要 3 秒才能到达目标位置，答案是 3。
可以证明 3 是从 S 到 D 所需的最小时间。

示例 2：

输入：land = [["D","X","*"],[".",".","."],[".",".","S"]]
输出：-1
解释：下面的图片逐秒模拟了土地的变化。蓝色的单元格被淹没，灰色的单元格是石头。
图片（0）显示了初始状态。正如你所看到的，无论我们选择哪条路径，我们都会在第三秒淹没。并且从 S 到 D 的最小路径需要 4 秒。
所以答案是 -1。

示例 3：

输入：land = [["D",".",".",".","*","."],[".","X",".","X",".","."],[".",".",".",".","S","."]]
输出：6
解释：可以证明我们可以在 6 秒内到达目标位置。同时也可以证明 6 是从 S 到 D 所需的最小秒数。

提示：

2 <= n, m <= 100
land 只由 "S", "D", ".", "*" 和 "X" 组成。
恰好有一个单元格等于 "S"。
恰好有一个单元格等于 "D"。

分析

先 bfs 一遍求出每个格子被淹的时间
再 bfs 一遍，不能走已经被淹的格子

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution:
    def minimumSeconds(self, land: List[List[str]]) -> int:
        m,n = len(land),len(land[0])
        d = defaultdict(list)
        for i in range(m):
            for j in range(n):
                d[land[i][j]].append((i,j))
        t = [[inf]*n for _ in range(m)]
        dq = d['*']
        for i,j in dq:
            t[i][j] = 0
        while dq:
            tmp,dq = dq,[]
            for i,j in tmp:
                for x,y in [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]:
                    if 0<=x<m and 0<=y<n and land[x][y]=='.' and t[x][y]==inf:
                        t[x][y] = t[i][j] + 1
                        dq.append((x,y))
        si,sj = d['S'][0]
        di,dj = d['D'][0]
        f = [[inf]*n for _ in range(m)]
        f[si][sj] = 0
        dq = [(si,sj,0)]
        while dq:
            tmp,dq = dq,[]
            for i,j,w in tmp:
                if (i,j)==(di,dj):
                    return w
                for x,y in [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]:
                    if 0<=x<m and 0<=y<n and land[x][y]!='X':
                        if f[x][y]==inf and w+1<t[x][y]:
                            f[x][y] = w+1
                            dq.append((x,y,w+1))
        return -1

647 ms

目录

2814：避免淹死并到达目的地的最短时间（★★）

题目

分析

解答