<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>

class Solution:
    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
        '''
        Intuition: For it to be possible to disconnect a graph with at most
        one cell means there should be one cell that's the bottleneck. If a path with
        that cell is removed, then the last node should be unreachable. 
        Thus, run BFS, and if a path exists, remove it and rerun BFS. There should be
        no existing path by the end of it.
        '''
        
        m, n = len(grid), len(grid[0])
        if m==n==1 or (m==1 and n==2) or (m==2 and n==1): return False

        def bfs(grid):
            '''returns coords of shortest path'''

            def get_path(parents):
                path = []
                child = (m-1,n-1)
                while parents[child] != (0,0):
                    path.append(parents[child])
                    child = path[-1]
                # path.append((0,0)) # don't want to flip (0,0) value to 0 later
                return path

            queue = [(0,0)]
            seen = {}
            goal = (m-1, n-1)
            while queue:
                parent = queue.pop()
                if parent == goal:
                    return get_path(seen)
                row, col = parent
                for i, j in [(row+1,col), (row,col+1)]:
                    if 0 <= i < m and 0 <= j < n and ((i,j) not in seen) and grid[i][j] == 1:
                        seen[(i,j)] = parent
                        queue.append((i,j))
            return []

        path = bfs(grid)
        
        if not path:
            return True

        # remove path
        for i, j in path:
            grid[i][j] = 0

        try_again = bfs(grid)
        return len(try_again) == 0
                
19800