class Solution {
public:
int minimumSeconds(vector<vector<string>>& land) {
}
};
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"
。原站题解