Skip to content

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

  • Time: $O(mn)$
  • Space: $O(m + n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  bool isPossibleToCutPath(vector<vector<int>>& grid) {
    if (!hasPath(grid, 0, 0))
      return true;
    // Reassign (0, 0) as 1.
    grid[0][0] = 1;
    return !hasPath(grid, 0, 0);
  }

 private:
  // Returns true is there's a path from (0, 0) to (m - 1, n - 1).
  // Also mark the visited path as 0 except (m - 1, n - 1).
  bool hasPath(vector<vector<int>>& grid, int i, int j) {
    if (i == grid.size() || j == grid[0].size())
      return false;
    if (i == grid.size() - 1 && j == grid[0].size() - 1)
      return true;
    if (grid[i][j] == 0)
      return false;

    grid[i][j] = 0;
    // Go down first. Since we use OR logic, we'll only mark one path.
    return hasPath(grid, i + 1, j) || hasPath(grid, i, j + 1);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public boolean isPossibleToCutPath(int[][] grid) {
    if (!hasPath(grid, 0, 0))
      return true;
    // Reassign (0, 0) as 1.
    grid[0][0] = 1;
    return !hasPath(grid, 0, 0);
  }

  // Returns true is there's a path from (0, 0) to (m - 1, n - 1).
  // Also mark the visited path as 0 except (m - 1, n - 1).
  private boolean hasPath(int[][] grid, int i, int j) {
    if (i == grid.length || j == grid[0].length)
      return false;
    if (i == grid.length - 1 && j == grid[0].length - 1)
      return true;
    if (grid[i][j] == 0)
      return false;

    grid[i][j] = 0;
    // Go down first. Since we use OR logic, we'll only mark one path.
    return hasPath(grid, i + 1, j) || hasPath(grid, i, j + 1);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
    # Returns True is there's a path from (0, 0) to (m - 1, n - 1).
    # Also mark the visited path as 0 except (m - 1, n - 1).
    def hasPath(i: int, j: int) -> bool:
      if i == len(grid) or j == len(grid[0]):
        return False
      if i == len(grid) - 1 and j == len(grid[0]) - 1:
        return True
      if grid[i][j] == 0:
        return False

      grid[i][j] = 0
      # Go down first. Since we use OR logic, we'll only mark one path.
      return hasPath(i + 1, j) or hasPath(i, j + 1)

    if not hasPath(0, 0):
      return True
    # Reassign (0, 0) as 1.
    grid[0][0] = 1
    return not hasPath(0, 0)