title
给你一个下标从 0 开始的 m x n 二进制 矩阵 grid 。你可以从一个格子 (row, col) 移动到格子 (row + 1, col) 或者 (row, col + 1) ，前提是前往的格子值为 1 。如果从 (0, 0) 到 (m - 1, n - 1) 没有任何路径，我们称该矩阵是 不连通 的。
你可以翻转 最多一个 格子的值（也可以不翻转）。你 不能翻转 格子 (0, 0) 和 (m - 1, n - 1) 。
如果可以使矩阵不连通，请你返回 true ，否则返回 false 。
注意 ，翻转一个格子的值，可以使它的值从 0 变 1 ，或从 1 变 0 。
示例 1：
输入：grid = [[1,1,1],[1,0,0],[1,1,1]]
输出：true
解释：按照上图所示我们翻转蓝色格子里的值，翻转后从 (0, 0) 到 (2, 2) 没有路径。
示例 2：
输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：false
解释：无法翻转至多一个格子，使 (0, 0) 到 (2, 2) 没有路径。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 10001 <= m * n <= 105grid[0][0] == grid[m - 1][n - 1] == 1
solution
判断是否有两次完全不同的路径，两次dfs，每次把当前路径去掉就行。
如果两次都可以到达终点，说明至少两次完全不同的路径。
class Solution:
def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
m, n = len(grid), len(grid[0])
def dfs(x, y):
if (x, y) == (m - 1, n - 1):
return True
grid[x][y] = 0
if x + 1 < m and grid[x + 1][y] == 1:
if dfs(x + 1, y):
return True
if y + 1 < n and grid[x][y + 1] == 1:
if dfs(x, y + 1):
return True
return False
return (not dfs(0, 0)) or (not dfs(0, 0))