# 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>& 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>& 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)