你能穿过矩阵的最后一天

难度: Hard

给你一个下标从 1 开始的二进制矩阵，其中 0 表示陆地，1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。

一开始在第 0 天，整个矩阵都是陆地。但每一天都会有一块新陆地被水淹没变成水域。给你一个下标从 1 开始的二维数组 cells ，其中 cells[i] = [r_i, c_i] 表示在第 i 天，第 r_i 行 c_i 列（下标都是从 1 开始）的陆地会变成水域（也就是 0 变成 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 <= row * col <= 2 * 10⁴
cells.length == row * col
1 <= r_i <= row
1 <= c_i <= col
cells 中的所有格子坐标都是唯一的。

Submission

运行时间: 126 ms

内存: 24.4 MB

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        visited = set()
        wait = set()
    
        def dfs(x, y):
            if y == col:
                return True
            for xx, yy in dirs:
                new_x, new_y = x + xx, y + yy
                if (new_x, new_y) in wait:
                    wait.remove((new_x, new_y))
                    visited.add((new_x, new_y))
                    if dfs(new_x, new_y):
                        return True
            return False
     
        for i, (x, y) in enumerate(cells):
            flag = False       
            if y == 1:
                flag = True 
            else:
                for xx, yy in dirs:
                    new_x, new_y = x + xx, y + yy
                    if (new_x, new_y) in visited:
                        flag = True
                        break       
            if flag:
                visited.add((x, y))
                if dfs(x, y):
                    return i
            # 暂未连通，丢入wait
            else:
                wait.add((x, y))

Explain

该题解采用深度优先搜索(DFS)来检测从最上面一行到最下面一行是否存在一条完全由陆地构成的路径。该方法逐天模拟每一块陆地被水淹没的过程。对于每一天淹没的陆地，算法检查该陆地的相邻格子是否已经访问过（即已经被淹没并验证过）。如果相邻的格子已被访问，算法会尝试从当前格子开始执行DFS，探索是否能够从顶部到达底部。使用两个集合管理状态：'visited' 存储已经被探索过的陆地格子，'wait' 存储等待探索的陆地格子。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        dirs = [(-1, 0), (0, -1), (0, 1), (1, 0)] # 修改为四个基本方向
        visited = set() # 存储已探索的格子
        wait = set() # 存储等待探索的格子
    
        def dfs(x, y):
            if y == col: # 到达最右边，表示成功从顶部到底部
                return True
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if (nx, ny) in wait: # 从等待集合中取格子尝试DFS
                    wait.remove((nx, ny))
                    visited.add((nx, ny))
                    if dfs(nx, ny):
                        return True
            return False
     
        for i, (x, y) in enumerate(cells):
            flag = False       
            if y == 1:
                flag = True # 第一列直接标记为True，尝试进行DFS
            else:
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if (nx, ny) in visited: # 检查相邻已探索的格子
                        flag = True
                        break       
            if flag:
                visited.add((x, y))
                if dfs(x, y):
                    return i + 1 # 返回的是第几天，所以+1
            else:
                wait.add((x, y)) # 当前格子未连通，添加到等待集合

Explore

在DFS实现中，移除等待集合中的元素并添加到已访问集合是为了防止重复访问同一个格子，这样可以避免无限循环和不必要的重复计算。这种处理方式有助于降低时间复杂度，使算法更加高效。此外，它还可以帮助算法正确地追踪已探索和未探索的格子，确保每个格子在适当的时间被访问，从而维护算法的正确性。

当陆地变为水域的格子位于第一列时，这意味着有可能形成从顶部到底部的直接路径，因此必须检查是否可以通过这个新变化的格子找到一条路径。如果相邻格子已经被访问过，这意味着从其他路径可能已经接近底部，因此需要重新检查从当前格子开始是否能到达底部。这种条件判断有助于减少不必要的DFS调用，因为只在可能形成路径的情况下才进行深入探索，从而提高算法的效率。

确实存在逻辑错误。在题解中提到的检查到达最右边列来认定成功路径的逻辑是不正确的。正确的逻辑应该是检查是否到达最下面一行。这个错误可能是由于对问题描述的误解造成的。在实际实现中，应当修正这部分逻辑，确保只有当DFS到达矩阵的最下面一行时，才判断为成功找到从顶部到底部的路径。

在最坏情况下，每次淹没一块陆地都可能触发一次完整的DFS探索，这会导致算法的性能显著下降，尤其是在大规模数据集上。因为每次淹没都可能需要探索整个矩阵的剩余部分，这样的重复探索会导致时间复杂度增加，可能达到O(n*m)的复杂度，其中n和m分别是矩阵的行数和列数。对于大规模数据集，这种方法可能不够高效，并且可能需要考虑更优化的算法，如并查集等，以改善性能。