23.06.30 Today’s Leetcode

1970. Last Day Where You Can Still Cross (hard)

TLE

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:

        m, n = col, row

        board = [[0 for _ in range(col)] for _ in range(row)]

        def check_cross(x):
            q = deque([(0, x)])
            while q:
                tar = q.popleft()
                p = [1, 0, -1, 0, 1]
                for i in range(4):
                    nx, ny = tar[0] + p[i], tar[1] + p[i + 1]
                    if nx < 0 or nx >= m or ny < 0 or ny >= n:
                        continue
                    if board[nx][ny] == 1:
                        continue
                    q.append((nx, ny))
                
                if tar[0] == m - 1:
                    return True
            
            return False

        def check():
            for i in range(n):
                if check_cross(i):
                    return True
            return False
        
        for i, v in enumerate(cells):
            x, y = v
            board[x - 1][y - 1] = 1
            if not check():
                return i - 1
        
        return 0

Binary Search Approach

class Solution:
    def isPossible(self, row, col, cells, day):
        grid = [[0] * col for _ in range(row)]
        queue = collections.deque()
        
        for r, c in cells[:day]:
            grid[r - 1][c - 1] = 1
            
        for i in range(col):
            if not grid[0][i]:
                queue.append((0, i))
                grid[0][i] = -1

        while queue:
            r, c = queue.popleft()
            if r == row - 1:
                return True
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < row and 0 <= nc < col and grid[nr][nc] == 0:
                    grid[nr][nc] = -1
                    queue.append((nr, nc))
                    
        return False
    
    
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        left, right = 1, row * col
        
        while left < right:
            mid = right - (right - left) // 2
            if self.isPossible(row, col, cells, mid):
                left = mid
            else:
                right = mid - 1
                
        return left