二进制矩阵中翻转最多一次使路径不连通

难度: Medium

给你一个下标从 0 开始的 m x n 二进制 矩阵 grid 。你可以从一个格子 (row, col) 移动到格子 (row + 1, col) 或者 (row, col + 1) ，前提是前往的格子值为 1 。如果从 (0, 0) 到 (m - 1, n - 1) 没有任何路径，我们称该矩阵是 不连通 的。

你可以翻转 最多一个 格子的值（也可以不翻转）。你 不能翻转 格子 (0, 0) 和 (m - 1, n - 1) 。

如果可以使矩阵不连通，请你返回 true ，否则返回 false 。

注意，翻转一个格子的值，可以使它的值从 0 变 1 ，或从 1 变 0 。

示例 1：

输入：grid = [[1,1,1],[1,0,0],[1,1,1]]
输出：true
解释：按照上图所示我们翻转蓝色格子里的值，翻转后从 (0, 0) 到 (2, 2) 没有路径。

示例 2：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：false
解释：无法翻转至多一个格子，使 (0, 0) 到 (2, 2) 没有路径。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
grid[0][0] == grid[m - 1][n - 1] == 1

Submission

运行时间: 36 ms

内存: 21.3 MB

class Solution:
    def isPossibleToCutPath(self, g: List[List[int]]) -> bool:
        m, n = len(g), len(g[0])
        def dfs(x: int, y: int) -> bool:  # 返回能否到达终点
            if x == m - 1 and y == n - 1: return True
            g[x][y] = 0  # 直接修改
            return x < m - 1 and g[x + 1][y] and dfs(x + 1, y) or                    y < n - 1 and g[x][y + 1] and dfs(x, y + 1)
        return not dfs(0, 0) or not dfs(0, 0)

Explain

本题解通过深度优先搜索（DFS）的方法，从矩阵的起点(0, 0)开始探索是否能到达终点(m-1, n-1)。DFS在探索过程中会直接修改原矩阵中的元素值来标记访问过的位置，以防止重复访问。若第一次DFS调用后无法到达终点，则矩阵原本就是不连通的，返回true。如果第一次DFS调用能到达终点，它会对矩阵进行修改，第二次调用DFS时将在被修改的矩阵上执行，检查是否仍然连通。如果第二次DFS调用无法到达终点，说明矩阵可以通过一次或不翻转变得不连通。

时间复杂度: O(m*n)

空间复杂度: O(m+n)

class Solution:
    def isPossibleToCutPath(self, g: List[List[int]]) -> bool:
        m, n = len(g), len(g[0])
        def dfs(x: int, y: int) -> bool:  # 探索路径到(x, y)是否能到达(m-1, n-1)
            if x == m - 1 and y == n - 1: return True  # 如果到达终点，返回True
            g[x][y] = 0  # 访问过的位置标记为0以防重复访问
            # 探索向下或向右移动，只有当下一个位置为1时才移动
            return x < m - 1 and g[x + 1][y] and dfs(x + 1, y) or y < n - 1 and g[x][y + 1] and dfs(x, y + 1)
        return not dfs(0, 0) or not dfs(0, 0)  # 如果第一次或第二次DFS调用返回False，则矩阵可以通过翻转变得不连通

Explore

在题解中，使用DFS两次在逻辑上看似可以在同一个矩阵进行，但实际上，第一次DFS在执行过程中已经修改了矩阵的状态，这可能会对第二次DFS产生影响。如果第一次DFS搜索后没有恢复矩阵到原始状态，第二次搜索将无法正确判断矩阵的连通性。因此，正确的做法应该在第一次DFS后将矩阵状态恢复，或者使用一个复制的矩阵状态进行第二次DFS，确保每次搜索的独立性和准确性。

在DFS中将访问过的位置标记为0是为了防止在搜索过程中重复访问相同的位置，这种做法确实会修改原始矩阵的数据。如果没有采取措施记录原始值并在适当时候恢复，这种修改是不可逆的，将导致原始矩阵数据丢失。因此，为了保持原始数据的完整性，可以在访问前保存原始值，并在DFS返回之前恢复，或者使用额外的数据结构（如访问标记数组）来跟踪访问状态，而不直接修改原矩阵。

题解中第一次DFS调用到达终点，意味着在当前矩阵配置下存在一条从起点到终点的路径。在没有进行翻转的情况下进行第二次DFS调用，其目的是在相同的路径条件下验证矩阵是否还是连通的。这里的关键是确保矩阵在两次调用间的状态没有被错误地改变（例如，第一次调用后应恢复所有修改），以确保第二次DFS的有效性。如果第一次DFS后未恢复矩阵，那么第二次DFS的结果可能不准确，因为它可能会错误地认为矩阵是不连通的。