<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 dfs(self, visited, i, j, grid, can_reach):
        if i == len(grid) - 1 and j == len(grid[0]) - 1:
            return True
        if can_reach[i][j]:
            return True
        offsets = [(0, 1), (1, 0)]
        for (oi, oj) in offsets:
            ni = i + oi
            nj = j + oj
            if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]) and grid[ni][nj] == 1 and (ni, nj) not in visited:
                visited.add((ni, nj))
                if self.dfs(visited, ni, nj, grid, can_reach):
                    can_reach[i][j] = True
                    
                visited.remove((ni, nj))
        return can_reach[i][j]

    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
        if len(grid) == 0 or len(grid[0]) <= 1:
            return False
        can_reach = [[False] * len(grid[0]) for _ in range(len(grid))]
        can_reach[-1][-1] = True
        self.dfs(set([(0, 0)]), 0, 0, grid, can_reach)
        offsets = [(0, 1), (1, 0)]
        q = collections.deque([(0, 0)])
        visited = set()
        while q:
            new_step = set()
            size = len(q)
            for _ in range(size):
                (i, j) = q.popleft()
                for (oi, oj) in offsets:
                    ni = i + oi
                    nj = j + oj
                    if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]) and (ni, nj) not in visited and can_reach[ni][nj]:
                        visited.add((ni, nj))
                        q.append((ni, nj))
                        new_step.add((ni, nj))
            if len(new_step) == 0:
                return True
            if len(new_step) == 1:
                if new_step != set([(len(grid) - 1, len(grid[0]) - 1)]):
                    print(q)
                    print(new_step)
                    print(set((len(grid) - 1, len(grid[0]) - 1)))
                    return True
                return False
        return False
                

                
        
        
34700