<p>You are given a <strong>0-indexed</strong> <code>m x n</code> <strong>binary</strong> matrix <code>grid</code>. You can move from a cell <code>(row, col)</code> to any of the cells <code>(row + 1, col)</code> or <code>(row, col + 1)</code> that has the value <code>1</code>.&nbsp;The matrix is <strong>disconnected</strong> if there is no path from <code>(0, 0)</code> to <code>(m - 1, n - 1)</code>.</p>

<p>You can flip the value of <strong>at most one</strong> (possibly none) cell. You <strong>cannot flip</strong> the cells <code>(0, 0)</code> and <code>(m - 1, n - 1)</code>.</p>

<p>Return <code>true</code> <em>if it is possible to make the matrix disconnect or </em><code>false</code><em> otherwise</em>.</p>

<p><strong>Note</strong> that flipping a cell changes its value from <code>0</code> to <code>1</code> or from <code>1</code> to <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/12/07/yetgrid2drawio.png" style="width: 441px; height: 151px;" />
<pre>
<strong>Input:</strong> grid = [[1,1,1],[1,0,0],[1,1,1]]
<strong>Output:</strong> true
<strong>Explanation:</strong> We can change the cell shown in the diagram above. There is no path from (0, 0) to (2, 2) in the resulting grid.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/12/07/yetgrid3drawio.png" />
<pre>
<strong>Input:</strong> grid = [[1,1,1],[1,0,1],[1,1,1]]
<strong>Output:</strong> false
<strong>Explanation:</strong> It is not possible to change at most one cell such that there is not path from (0, 0) to (2, 2).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 1000</code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
	<li><code>grid[0][0] == grid[m - 1][n - 1] == 1</code></li>
</ul>

from typing import List, Tuple
import unittest

def find_path(
        matrix: List[List[int]],
        dir1: Tuple[int, int],
        dir2: Tuple[int, int]
        ) -> List[Tuple[int, int]]:
    m = len(matrix)  # i
    n = len(matrix[0])  # j
    # items: (i, j, path to (i, j), direction to grow
    q = [(((0, 0),), dir2), (((0, 0),), dir1)]
    while len(q):
        (path, direction) = q.pop()
        (i, j) = path[-1]
        i_next = i + direction[0]
        if i_next >= m:
            continue
        j_next = j + direction[1]
        if j_next >= n:
            continue
        if not matrix[i_next][j_next]:
            continue
        path_next = (*path, (i_next, j_next))
        if (i_next == m - 1) and (j_next == n - 1):
            return path_next                               # return
        q.append((path_next, dir2))
        q.append((path_next, dir1))


class Solution:
    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
        if len(grid) == 1 and len(grid[0]) == 1:
            return False
        path1 = find_path(grid, (1, 0), (0, 1))
        if not path1:
            return True
        path2 = find_path(grid, (0, 1), (1, 0))
        if not path2:
            return True
        shared = set(path1).intersection(path2)
        return len(shared) > 2

23800