Medium

题目描述

给你一个下标从 0 开始的 m x n 二进制矩阵 grid。你可以从一个格子 (row, col) 移动到任一个值为 1 的格子 (row + 1, col) 或 (row, col + 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^5
  • grid[i][j] 不是 0 就是 1
  • grid[0][0] == grid[m - 1][n - 1] == 1

解题思路

这道题的核心思想是：如果存在两条不相交的路径从起点到终点，那么翻转任何一个格子都无法断开连通性。

解题思路有两种主要方法：

方法一：网络流最小割

  • 将问题转化为最小割问题
  • 如果最小割大于1，说明存在多条不相交路径，无法通过翻转一个格子断开
  • 可以使用Dinic算法或其他最大流算法求解

方法二：DFS路径搜索（推荐）

  • 先找到一条从起点到终点的路径，并将路径上的格子（除起点终点）标记为已访问
  • 然后尝试再找一条路径，如果能找到第二条路径，说明存在两条不相交路径
  • 如果只能找到一条路径，则可以通过翻转路径上任意一个格子来断开连通

具体实现：

  1. 使用DFS找到第一条路径，并将路径上的格子置0（起点终点除外）
  2. 再次使用DFS尝试寻找第二条路径
  3. 如果找到第二条路径，返回false；否则返回true

时间复杂度为O(m×n)，空间复杂度为O(m×n)。这种方法直观且高效，适合这道题的约束条件。

代码实现

class Solution {
public:
    bool isPossibleToCutPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 找第一条路径
        if (!dfs(grid, 0, 0, m, n)) {
            return true; // 原本就不连通
        }
        
        // 恢复起点
        grid[0][0] = 1;
        
        // 尝试找第二条路径
        return !dfs(grid, 0, 0, m, n);
    }
    
private:
    bool dfs(vector<vector<int>>& grid, int i, int j, int m, int n) {
        if (i == m - 1 && j == n - 1) {
            return true;
        }
        
        if (i >= m || j >= n || grid[i][j] == 0) {
            return false;
        }
        
        // 标记当前格子为已访问（除了终点）
        if (!(i == m - 1 && j == n - 1)) {
            grid[i][j] = 0;
        }
        
        // 尝试向下和向右移动
        return dfs(grid, i + 1, j, m, n) || dfs(grid, i, j + 1, m, n);
    }
};

class Solution:
    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        
        def dfs(i, j):
            if i == m - 1 and j == n - 1:
                return True
            
            if i >= m or j >= n or grid[i][j] == 0:
                return False
            
            # 标记当前格子为已访问（除了终点）
            if not (i == m - 1 and j == n - 1):
                grid[i][j] = 0
            
            # 尝试向下和向右移动
            return dfs(i + 1, j) or dfs(i, j + 1)
        
        # 找第一条路径
        if not dfs(0, 0):
            return True  # 原本就不连通
        
        # 恢复起点
        grid[0][0] = 1
        
        # 尝试找第二条路径
        return not dfs(0, 0)

public class Solution {
    public bool IsPossibleToCutPath(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // 找第一条路径
        if (!Dfs(grid, 0, 0, m, n)) {
            return true; // 原本就不连通
        }
        
        // 恢复起点
        grid[0][0] = 1;
        
        // 尝试找第二条路径
        return !Dfs(grid, 0, 0, m, n);
    }
    
    private bool Dfs(int[][] grid, int i, int j, int m, int n) {
        if (i == m - 1 && j == n - 1) {
            return true;
        }
        
        if (i >= m || j >= n || grid[i][j] == 0) {
            return false;
        }
        
        // 标记当前格子为已访问（除了终点）
        if (!(i == m - 1 && j == n - 1)) {
            grid[i][j] = 0;
        }
        
        // 尝试向下和向右移动
        return Dfs(grid, i + 1, j, m, n) || Dfs(grid, i, j + 1, m, n);
    }
}

var isPossibleToCutPath = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    function hasPath(grid) {
        const visited = Array(m).fill(null).map(() => Array(n).fill(false));
        
        function dfs(i, j) {
            if (i === m - 1 && j === n - 1) return true;
            if (i >= m || j >= n || grid[i][j] === 0 || visited[i][j]) return false;
            
            visited[i][j] = true;
            return dfs(i + 1, j) || dfs(i, j + 1);
        }
        
        return dfs(0, 0);
    }
    
    if (!hasPath(grid)) return true;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if ((i === 0 && j === 0) || (i === m - 1 && j === n - 1)) continue;
            
            const original = grid[i][j];
            grid[i][j] = 0;
            
            if (!hasPath(grid)) {
                return true;
            }
            
            grid[i][j] = original;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m × n)最多进行两次DFS遍历，每次最多访问所有格子
空间复杂度O(m × n)递归调用栈的深度最多为m + n - 2

相关题目