难度: Hard
Submission
运行时间: 273 ms
内存: 18.2 MB
from typing import List
class Solution:
def minimumSeconds(self, land: List[List[str]]) -> int:
m = len(land)
n = len(land[0])
flooded = []
dest = None
src = None
for i in range(m):
for j in range(n):
if land[i][j] == '*':
land[i][j] = 0
flooded.append((i, j))
elif land[i][j] == 'D':
dest = (i, j)
elif land[i][j] == 'S':
land[i][j] = '.'
src = (i, j)
t = 1
while flooded:
nxt = []
for i, j in flooded:
if i != 0 and land[i - 1][j] == '.':
land[i - 1][j] = t
nxt.append((i - 1, j))
if i != m - 1 and land[i + 1][j] == '.':
land[i + 1][j] = t
nxt.append((i + 1, j))
if j != 0 and land[i][j - 1] == '.':
land[i][j - 1] = t
nxt.append((i, j - 1))
if j != n - 1 and land[i][j + 1] == '.':
land[i][j + 1] = t
nxt.append((i, j + 1))
t += 1
flooded = nxt
#print(land)
x = [src]
t = -1
while x:
nxt = []
for i, j in x:
if (i, j) == dest:
return -t - 1
if i != 0 and land[i - 1][j] != 'X' and (str(land[i - 1][j]) in '.D' or land[i - 1][j] > abs(t)):
land[i - 1][j] = t
nxt.append((i - 1, j))
if i != m - 1 and land[i + 1][j] != 'X' and (str(land[i + 1][j]) in '.D' or land[i + 1][j] > abs(t)):
land[i + 1][j] = t
nxt.append((i + 1, j))
if j != 0 and land[i][j - 1] != 'X' and (str(land[i][j - 1]) in '.D' or land[i][j - 1] > abs(t)):
land[i][j - 1] = t
nxt.append((i, j - 1))
if j != n - 1 and land[i][j + 1] != 'X' and (str(land[i][j + 1]) in '.D' or land[i][j + 1] > abs(t)):
land[i][j + 1] = t
nxt.append((i, j + 1))
t -= 1
#print(land)
x = nxt
return -1
Explain
该题解使用了两个广度优先搜索（BFS）来解决问题。第一个BFS从已经被淹没的地方开始，计算每个点被淹没的时间。第二个BFS从起点开始，寻找到达终点的最短路径，同时确保在每一步行走时，该位置尚未被淹没。如果可以到达终点，则返回所需的最短时间，否则返回-1。
时间复杂度: O(mn)
空间复杂度: O(mn)
from typing import List
class Solution:
def minimumSeconds(self, land: List[List[str]]) -> int:
m = len(land)
n = len(land[0])
flooded = []
dest = None
src = None
for i in range(m):
for j in range(n):
if land[i][j] == '*':
land[i][j] = 0
flooded.append((i, j))
elif land[i][j] == 'D':
dest = (i, j)
elif land[i][j] == 'S':
land[i][j] = '.'
src = (i, j)
t = 1
while flooded:
nxt = []
for i, j in flooded:
if i != 0 and land[i - 1][j] == '.':
land[i - 1][j] = t
nxt.append((i - 1, j))
if i != m - 1 and land[i + 1][j] == '.':
land[i + 1][j] = t
nxt.append((i + 1, j))
if j != 0 and land[i][j - 1] == '.':
land[i][j - 1] = t
nxt.append((i, j - 1))
if j != n - 1 and land[i][j + 1] == '.':
land[i][j + 1] = t
nxt.append((i, j + 1))
t += 1
flooded = nxt
x = [src]
t = -1
while x:
nxt = []
for i, j in x:
if (i, j) == dest:
return -t - 1
if i != 0 and land[i - 1][j] != 'X' and (str(land[i - 1][j]) in '.D' or land[i - 1][j] > abs(t)):
land[i - 1][j] = t
nxt.append((i - 1, j))
if i != m - 1 and land[i + 1][j] != 'X' and (str(land[i + 1][j]) in '.D' or land[i + 1][j] > abs(t)):
land[i + 1][j] = t
nxt.append((i + 1, j))
if j != 0 and land[i][j - 1] != 'X' and (str(land[i][j - 1]) in '.D' or land[i][j - 1] > abs(t)):
land[i][j - 1] = t
nxt.append((i, j - 1))
if j != n - 1 and land[i][j + 1] != 'X' and (str(land[i][j + 1]) in '.D' or land[i][j + 1] > abs(t)):
land[i][j + 1] = t
nxt.append((i, j + 1))
t -= 1
x = nxt
return -1
Explore
题解选择使用两次广度优先搜索（BFS）主要是因为BFS能够有效地找到从一点到另一点的最短路径，这在本题中非常关键。第一个BFS用于确定每个位置被淹没的时间，保证计算的是从最初的水源开始的全局最短淹没时间。第二个BFS用于寻找在不被淹没的情况下，从起点到终点的最短路径。使用DFS可能会导致过早探索深层节点，无法保证找到的是最短路径。而迪杰斯特拉算法在这里不是特别适用，因为它主要解决带权重的最短路径问题，而本题中每一步的权重相同，且需要额外考虑时间限制（淹没时间），这使得BFS成为更合适的选择。
题解中确实没有明确说明处理这些特殊边界条件的细节。在实际实现中，如果起点'S'已经在初始状态被淹没（例如起点就在'*'处或者被立即淹没的地方），则无法开始正常的路径搜索，应该立即返回-1，表示无法到达目的地。同样，如果终点'D'在开始搜索之前已被淹没，也应返回-1。这些情况需要在算法开始前进行检查，以确保输入数据的有效性和搜索的可行性。
在代码中，变量`t`被用于两个不同的目的确实是一种特别的设计考虑。在第一个BFS中，`t`表示时间，用来记录地图上每个点被淹没的时间。这样可以确保在第二个BFS进行时，每一步移动都能检查该点是否已被淹没。在第二个BFS中，`t`被用作反向时间计数器，用于跟踪从起点到当前点的步数（即时间）。使用单个变量来表示不同的时间概念（淹没时间和移动时间），简化了代码的复杂性，同时也有效地利用了变量来控制算法的流程。