Leetcode 2556. Disconnect Path in a Binary Matrix by at Most One Flip

[Woodyiiiiiii]

这是一道关于割点的问题。我们可以用路径覆盖，第一次DFS将连接路径上的节点置为0，第二次继续判断是否能连通。

注意到路线的移动只能往右边和下边，所以我们不用考虑回环和可能覆盖其他连接路径的问题。

class Solution {

    private final int[][] dirs = new int[][]{{0,1},{1,0}};

    public boolean isPossibleToCutPath(int[][] grid) {
        if (grid.length == 1 && grid[0].length == 2) return false;
        boolean isConnected = dfs(grid, 0, 0);
        grid[grid.length - 1][grid[0].length - 1] = 1;
        return !isConnected || !dfs(grid, 0, 0);
    }

    private boolean dfs(int[][] grid, int i, int j) {
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            return true;
        }
        grid[i][j] = 0;
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) {
                continue;
            }
            if (dfs(grid, x, y)) {
                return true;
            }
        }
        return false;
    }

}

还有一个计算对角线的方法：https://leetcode.com/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/solutions/3141701/python-count-points-on-diagonal/

---

• 2556. Disconnect Path in a Binary Matrix by at Most One Flip