Approach
Breadth-first search
For Minimum Time Takes to Reach Destination Without Drowning, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 67 lines of Python from the credited upstream file 2814.py.
- The implementation visibly relies on sequence storage, ordered lookup, work queue.
- No explicit loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution:2 def minimumSeconds(self, land: list[list[str]]) -> int:3 self.DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))4 m = len(land)5 n = len(land[0])6 floodDist = self._getFloodDist(land)7 startPos = self._getStartPos(land, 'S')8 9 q = collections.deque([startPos])10 seen = {startPos}11 12 step = 113 while q:14 for _ in range(len(q)):15 i, j = q.popleft()16 for dx, dy in self.DIRS:17 x = i + dx18 y = j + dy19 if x < 0 or x == m or y < 0 or y == n:20 continue21 if land[x][y] == 'D':22 return step23 if floodDist[x][y] <= step or land[x][y] == 'X' or (x, y) in seen:24 continue25 q.append((x, y))26 seen.add((x, y))27 step += 128 29 return -130 31 def _getFloodDist(self, land: list[list[str]]) -> list[list[int]]:32 m = len(land)33 n = len(land[0])34 dist = [[math.inf] * n for _ in range(m)]35 q = collections.deque()36 seen = set()37 38 for i, row in enumerate(land):39 for j, cell in enumerate(row):40 if cell == '*':41 q.append((i, j))42 seen.add((i, j))43 44 d = 045 while q:46 for _ in range(len(q)):47 i, j = q.popleft()48 dist[i][j] = d49 for dx, dy in self.DIRS:50 x = i + dx51 y = j + dy52 if x < 0 or x == m or y < 0 or y == n:53 continue54 if land[x][y] in 'XD' or (x, y) in seen:55 continue56 q.append((x, y))57 seen.add((x, y))58 d += 159 60 return dist61 62 def _getStartPos(self, land: list[list[str]], c: str) -> tuple[int, int]:63 for i, row in enumerate(land):64 for j, cell in enumerate(row):65 if cell == c:66 return i, j67