I think of the matrix as getting more and more flooded each day, so instead of checking every day naively, I binary-search on the answer. For any given day d, I temporarily mark the first d cells in cells as water, then I check whether there is still a path of land from the top row to the bottom using BFS (or DFS). I start the search from every land cell in the top row and try to walk only through land. If I can still reach the bottom, then crossing is possible on day d, so I try a later day; if not, I try an earlier day. This way, I efficiently narrow down to the last day when crossing is still possible.
from collections import deque
class Solution:
def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
directions = [(1,0), (-1,0), (0,1), (0,-1)]
def can_cross(day):
grid = [[0] * col for _ in range(row)]
for i in range(day):
r, c = cells[i]
grid[r-1][c-1] = 1
q = deque()
visited = [[False] * col for _ in range(row)]
for j in range(col):
if grid[0][j] == 0:
q.append((0, j))
visited[0][j] = True
while q:
x, y = q.popleft()
if x == row - 1:
return True
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < row and 0 <= ny < col and not visited[nx][ny] and grid[nx][ny] == 0:
visited[nx][ny] = True
q.append((nx, ny))
return False
left, right = 0, len(cells)
while left < right:
mid = (left + right + 1) // 2
if can_cross(mid):
left = mid
else:
right = mid - 1
return left- Time: O((row * col) * log(row * col))
- Space: O(row * col)
