1970. 最后一天还能穿越的日子

Hard

题目描述

有一个基于 1 的二进制矩阵，其中 0 表示陆地，1 表示水。给你整数 row 和 col，分别表示矩阵的行数和列数。

最初在第 0 天，整个矩阵都是陆地。但是，每天都会有一个新的单元格被水淹没。给你一个基于 1 的二维数组 cells，其中 cells[i] = [ri, ci] 表示在第 i 天，第 ri 行第 ci 列的单元格（基于 1 的坐标）将被水覆盖（即变为 1）。

你想找到最后一天，仍然可以通过只在陆地单元格上行走从顶部走到底部。你可以从顶行的任何单元格开始，到底行的任何单元格结束。你只能在四个基本方向（左、右、上、下）移动。

返回仍然可以通过只在陆地单元格上行走从顶部走到底部的最后一天。

示例 1：

输入：row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
输出：2
解释：上图描绘了从第 0 天开始矩阵每天的变化。
可以从上到下穿越的最后一天是第 2 天。

示例 2：

输入：row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
输出：1
解释：上图描绘了从第 0 天开始矩阵每天的变化。
可以从上到下穿越的最后一天是第 1 天。

示例 3：

输入：row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
输出：3
解释：上图描绘了从第 0 天开始矩阵每天的变化。
可以从上到下穿越的最后一天是第 3 天。

约束条件：

2 <= row, col <= 2 * 10^4
4 <= row * col <= 2 * 10^4
cells.length == row * col
1 <= ri <= row
1 <= ci <= col
cells 的所有值都是唯一的

解题思路

这道题要求找到最后一天还能从矩阵顶部走到底部的日子。这是一个经典的二分搜索 + 图遍历问题。

核心思路：

我们需要找到一个临界点：在某一天之后，就无法从顶部到达底部了
这个问题具有单调性：如果第 k 天无法穿越，那么第 k+1 天也一定无法穿越
因此可以使用二分搜索来找到最后一天能穿越的日子

算法步骤：

使用二分搜索在 [0, cells.length-1] 范围内搜索
对于每个中间值 mid，检查在第 mid 天是否还能从顶部到达底部
检查连通性可以使用 BFS/DFS 或并查集
如果第 mid 天能穿越，说明答案在右半部分；否则在左半部分

实现细节：

为了检查第 day 天的连通性，需要先将前 day 个单元格标记为水
然后从第一行的任意陆地开始 BFS/DFS，看能否到达最后一行
使用并查集的话，可以维护一个虚拟的顶部节点和底部节点，检查它们是否连通

推荐使用 二分搜索 + BFS 的方法，思路清晰且容易实现。

代码实现

class Solution {
public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        int left = 0, right = cells.size() - 1;
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canCross(row, col, cells, mid)) {
                result = mid + 1; // mid是第几个cell，天数要+1
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
private:
    bool canCross(int row, int col, vector<vector<int>>& cells, int day) {
        vector<vector<int>> grid(row, vector<int>(col, 0));
        
        // 将前day+1个单元格标记为水
        for (int i = 0; i <= day; i++) {
            grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
        }
        
        // BFS从第一行开始
        queue<pair<int, int>> q;
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        
        // 将第一行的陆地加入队列
        for (int j = 0; j < col; j++) {
            if (grid[0][j] == 0) {
                q.push({0, j});
                visited[0][j] = true;
            }
        }
        
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            
            // 如果到达最后一行，返回true
            if (x == row - 1) {
                return true;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if (nx >= 0 && nx < row && ny >= 0 && ny < col && 
                    !visited[nx][ny] && grid[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        
        return false;
    }
};

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        left, right = 0, len(cells) - 1
        result = 0
        
        while left <= right:
            mid = (left + right) // 2
            if self.canCross(row, col, cells, mid):
                result = mid + 1  # mid是第几个cell，天数要+1
                left = mid + 1
            else:
                right = mid - 1
        
        return result
    
    def canCross(self, row: int, col: int, cells: List[List[int]], day: int) -> bool:
        grid = [[0] * col for _ in range(row)]
        
        # 将前day+1个单元格标记为水
        for i in range(day + 1):
            grid[cells[i][0] - 1][cells[i][1] - 1] = 1
        
        # BFS从第一行开始
        from collections import deque
        queue = deque()
        visited = [[False] * col for _ in range(row)]
        
        # 将第一行的陆地加入队列
        for j in range(col):
            if grid[0][j] == 0:
                queue.append((0, j))
                visited[0][j] = True
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while queue:
            x, y = queue.popleft()
            
            # 如果到达最后一行，返回True
            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
                    queue.append((nx, ny))
        
        return False

public class Solution {
    public int LatestDayToCross(int row, int col, int[][] cells) {
        int left = 0, right = cells.Length - 1;
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (CanCross(row, col, cells, mid)) {
                result = mid + 1; // mid是第几个cell，天数要+1
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    private bool CanCross(int row, int col, int[][] cells, int day) {
        int[,] grid = new int[row, col];
        
        // 将前day+1个单元格标记为水
        for (int i = 0; i <= day; i++) {
            grid[cells[i][0] - 1, cells[i][1] - 1] = 1;
        }
        
        // BFS从第一行开始
        Queue<(int, int)> queue = new Queue<(int, int)>();
        bool[,] visited = new bool[row, col];
        
        // 将第一行的陆地加入队列
        for (int j = 0; j < col; j++) {
            if (grid[0, j] == 0) {
                queue.Enqueue((0, j));
                visited[0, j] = true;
            }
        }
        
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        
        while (queue.Count > 0) {
            var (x, y) = queue.Dequeue();
            
            // 如果到达最后一行，返回true
            if (x == row - 1) {
                return true;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if (nx >= 0 && nx < row && ny >= 0 && ny < col && 
                    !visited[nx, ny] && grid[nx, ny] == 0) {
                    visited[nx, ny] = true;
                    queue.Enqueue((nx, ny));
                }
            }
        }
        
        return false;
    }
}

var latestDayToCross = function(row, col, cells) {
    let left = 0, right = cells.length - 1;
    let result = 0;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (canCross(row, col, cells, mid)) {
            result = mid + 1; // mid是第几个cell，天数要+1
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};

function canCross(row, col, cells, day) {
    const grid = Array(row).fill().map(() => Array(col).fill(0));
    
    // 将前day+1个单元格标记为水
    for (let i = 0; i <= day; i++) {
        grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
    }
    
    // BFS从第一行开始
    const queue = [];
    const visited = Array(row).fill().map(() => Array(col).fill(false));
    
    // 将第一行的陆地加入队列
    for (let j = 0; j < col; j++) {
        if (grid[0][j]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

算法	时间复杂度	空间复杂度
二分搜索 + BFS	O(row × col × log(row × col))	O(row × col)

解释：

时间复杂度：二分搜索需要 O(log(row × col)) 次迭代，每次迭代中的 BFS 需要 O(row × col) 时间
空间复杂度：需要 O(row × col) 的空间来存储网格、访问状态和 BFS 队列

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目