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

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

给你一个下标从 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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool isPossibleToCutPath(vector<vector<int>>& grid) { } };

golang 解法, 执行用时: 96 ms, 内存消耗: 7.6 MB, 提交时间: 2023-02-06 10:31:47

func isPossibleToCutPath(g [][]int) bool {
    m, n := len(g), len(g[0])
    var dfs func(int, int) bool
    dfs = func(x, y int) bool { // 返回能否到达终点
        if x == m-1 && y == n-1 {
            return true
        }
        g[x][y] = 0 // 直接修改，同时保证每个点至多访问一次
        return x < m-1 && g[x+1][y] > 0 && dfs(x+1, y) ||
               y < n-1 && g[x][y+1] > 0 && dfs(x, y+1)
    }
    return !dfs(0, 0) || !dfs(0, 0)
}

cpp 解法, 执行用时: 84 ms, 内存消耗: 36.5 MB, 提交时间: 2023-02-06 10:31:14

class Solution {
public:
    bool isPossibleToCutPath(vector<vector<int>> &g) {
        int m = g.size(), n = g[0].size();
        function<bool(int, int)> dfs = [&](int x, int y) -> bool { // 返回能否到达终点
            if (x == m - 1 && y == n - 1) return true;
            g[x][y] = 0; // 直接修改
            return x < m - 1 && g[x + 1][y] && dfs(x + 1, y) ||
                   y < n - 1 && g[x][y + 1] && dfs(x, y + 1);
        };
        return !dfs(0, 0) || !dfs(0, 0);
    }
};

java 解法, 执行用时: 0 ms, 内存消耗: 50.3 MB, 提交时间: 2023-02-06 10:30:58

class Solution {
    private int[][] g;
    private int m, n;

    public boolean isPossibleToCutPath(int[][] grid) {
        g = grid; m = g.length; n = g[0].length;
        return !dfs(0, 0) || !dfs(0, 0);
    }

    private boolean dfs(int x, int y) { // 返回能否到达终点
        if (x == m - 1 && y == n - 1) return true;
        g[x][y] = 0; // 直接修改
        return x < m - 1 && g[x + 1][y] > 0 && dfs(x + 1, y) ||
               y < n - 1 && g[x][y + 1] > 0 && dfs(x, y + 1);
    }
}

python3 解法, 执行用时: 56 ms, 内存消耗: 19 MB, 提交时间: 2023-02-06 10:29:44

'''
转换成求上下轮廓是否相交

上轮廓：优先向右走，其次向下走
下轮廓：优先向下走，其次向右走
'''
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)

上一题

下一题

详情