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

1/**
2 * [2556] Disconnect Path in a Binary Matrix by at Most One Flip
3 *
4 * 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).
5 * You can flip the value of at most one (possibly none) cell. You cannot flip the cells (0, 0) and (m - 1, n - 1).
6 * Return true if it is possible to make the matrix disconnect or false otherwise.
7 * Note that flipping a cell changes its value from 0 to 1 or from 1 to 0.
8 *  
9 * <strong class="example">Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2022/12/07/yetgrid2drawio.png" style="width: 441px; height: 151px;" />
11 * Input: grid = [[1,1,1],[1,0,0],[1,1,1]]
12 * Output: true
13 * Explanation: We can change the cell shown in the diagram above. There is no path from (0, 0) to (2, 2) in the resulting grid.
14 * 
15 * <strong class="example">Example 2:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2022/12/07/yetgrid3drawio.png" />
17 * Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
18 * Output: false
19 * Explanation: It is not possible to change at most one cell such that there is not path from (0, 0) to (2, 2).
20 * 
21 *  
22 * Constraints:
23 * 
24 * 	m == grid.length
25 * 	n == grid[i].length
26 * 	1 <= m, n <= 1000
27 * 	1 <= m * n <= 10^5
28 * 	grid[i][j] is either 0 or 1.
29 * 	grid[0][0] == grid[m - 1][n - 1] == 1
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/
35// discuss: https://leetcode.com/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn is_possible_to_cut_path(grid: Vec<Vec<i32>>) -> bool {
41        false
42    }
43}
44
45// submission codes end
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test_2556() {
53    }
54}
55