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
35
36
37
38
39
40
41
42
| import collections
class Solution:
def minimumSeconds(self, land: List[List[str]]) -> int:
rows, cols = len(land), len(land[0])
floodQueue = collections.deque()
moveQueue = collections.deque()
for i in range(rows):
for j in range(cols):
if land[i][j] == "S": moveQueue.append((i, j))
if land[i][j] == "*": floodQueue.append((i, j))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
seconds = 0
while moveQueue:
floodLen, moveLen = len(floodQueue), len(moveQueue)
# Simulate the flood
for _ in range(floodLen):
x, y = floodQueue.popleft()
for dx, dy in directions:
newX, newY = x + dx, y + dy
if 0 <= newX < rows and 0 <= newY < cols and land[newX][newY] == ".":
land[newX][newY] = "*"
floodQueue.append((newX, newY))
# Move the person from 'S' to 'D'
for _ in range(moveLen):
x, y = moveQueue.popleft()
if land[x][y] == "D":
return seconds
for dx, dy in directions:
newX, newY = x + dx, y + dy
if 0 <= newX < rows and 0 <= newY < cols and (land[newX][newY] == "." or land[newX][newY] == "D"):
if land[newX][newY] != "D": land[newX][newY] = "*"
moveQueue.append((newX, newY))
seconds += 1
return -1
|