Disconnect path in a binary matrix by at most one flip

Array Dynamic Programming Depth-First Search Breadth-First Search Matrix

27.8% acceptance

Feb 25, 2026

636

You are given a 0-indexed m x n binary matrix grid. You can move from a cell (row, col) to any of the cells (row + 1, col) or (row, col + 1) that has the value 1. The matrix is disconnected if there is no path from (0, 0) to (m - 1, n - 1). You can flip the value of at most one (possibly none) cell. You cannot flip the cells (0, 0) and (m - 1, n - 1). Return true if it is possible to make the matrix disconnect or false otherwise. Note that flipping a cell changes its value from 0 to 1 or from 1 to 0.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_possible_to_cut_path(grid: Vec<Vec<i32>>) -> bool {
    let m = grid.len();
    let n = grid[0].len();
    let mut g = grid;

    // DFS pass 1: mark path cells as visited (set to 2)
    fn dfs(g: &mut Vec<Vec<i32>>, r: usize, c: usize, m: usize, n: usize) -> bool {
      if r == m - 1 && c == n - 1 {
        return true;
      }
      g[r][c] = 2; // mark visited on first pass
      // Move down
      if r + 1 < m && g[r + 1][c] == 1 && dfs(g, r + 1, c, m, n) {
        return true;
      }
      // Move right
      if c + 1 < n && g[r][c + 1] == 1 && dfs(g, r, c + 1, m, n) {
        return true;
      }
      false
    }

    // First DFS: find a path, mark it
    let found1 = dfs(&mut g, 0, 0, m, n);
    if !found1 {
      return true; // already disconnected
    }

    // Unmark start and end so second DFS can use them
    g[0][0] = 1;
    g[m - 1][n - 1] = 1;

    // Second DFS: try to find another path (avoiding cells marked 2)
    fn dfs2(g: &mut Vec<Vec<i32>>, r: usize, c: usize, m: usize, n: usize) -> bool {
      if r == m - 1 && c == n - 1 {
        return true;
      }
      if g[r][c] != 1 {
        return false;
      }
      g[r][c] = 3; // mark visited on second pass
      if r + 1 < m && g[r + 1][c] == 1 && dfs2(g, r + 1, c, m, n) {
        return true;
      }
      if c + 1 < n && g[r][c + 1] == 1 && dfs2(g, r, c + 1, m, n) {
        return true;
      }
      false
    }

    let found2 = dfs2(&mut g, 0, 0, m, n);
    !found2
  }
}