There is a 1-based binary matrix where 0 represents land and 1 represents water. You are given integers row and col representing the number of rows and columns in the matrix, respectively. Initially on day 0, the entire matrix is land. However, each

latestDayToCross.js

/**
 * @param {number} row
 * @param {number} col
 * @param {number[][]} cells
 * @return {number}
 */
var latestDayToCross = function(row, col, cells) {
    // Helper: check if it's possible to cross on a given day
    function canCross(day) {
        // Build a grid where 1 = water, 0 = land
        const grid = Array.from({ length: row }, () => Array(col).fill(0));

        // Flood the first `day` cells
        for (let i = 0; i < day; i++) {
            const r = cells[i][0] - 1; // convert to 0-based
            const c = cells[i][1] - 1;
            grid[r][c] = 1; // water
        }

        // BFS queue
        const queue = [];

        // Visited matrix
        const visited = Array.from({ length: row }, () => Array(col).fill(false));

        // Add all land cells in the top row to the queue
        for (let c = 0; c < col; c++) {
            if (grid[0][c] === 0) {
                queue.push([0, c]);
                visited[0][c] = true;
            }
        }

        // Directions: up, down, left, right
        const dirs = [[1,0], [-1,0], [0,1], [0,-1]];

        // BFS traversal
        while (queue.length > 0) {
            const [r, c] = queue.shift();

            // If we reached the bottom row, crossing is possible
            if (r === row - 1) return true;

            // Explore neighbors
            for (const [dr, dc] of dirs) {
                const nr = r + dr;
                const nc = c + dc;

                // Bounds check + must be land + not visited
                if (
                    nr >= 0 && nr < row &&
                    nc >= 0 && nc < col &&
                    grid[nr][nc] === 0 &&
                    !visited[nr][nc]
                ) {
                    visited[nr][nc] = true;
                    queue.push([nr, nc]);
                }
            }
        }

        // No path found
        return false;
    }

    // Binary search for the last day we can cross
    let left = 1;
    let right = cells.length;
    let answer = 0;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (canCross(mid)) {
            // Crossing is possible → try later days
            answer = mid;
            left = mid + 1;
        } else {
            // Crossing is not possible → try earlier days
            right = mid - 1;
        }
    }

    return answer;
};