LC 6305. 二进制矩阵中翻转最多一次使路径不连通
https://leetcode.cn/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/
这题一开始一直没有搞清楚思路，始终在一种分析的思路上：如果相邻两行或者是两列满足某种条件的话，那么就可以通过修改某个点，让整个图不连通。
当然最开始也考虑过，如果有两条不想交的路径的话，那么就可以确保图肯定是联通的，不过之前好像没有这类型的题目。
如果按照“查找两条不相交的路径”的话，其实实现起来不难：第一次随便寻找一条路，第二次搜索的时候避开第一条路就好了。
搜索路径的时候最好使用动态规划 `dp[i][j]` 表示是否可以从i,j出发到达终点，然后我们可以通过dp来构建路径。第二次搜索的时候，直接修改graph将上一次搜索路径的点设置为0就行。
class Solution:
def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
n, m = len(grid), len(grid[0])
def search():
dp = [[0] * m for _ in range(n)]
dp[-1][-1] = 1
for i in reversed(range(n)):
for j in reversed(range(m)):
if grid[i][j] == 0: continue
if (i + 1) < n and dp[i + 1][j] == 1:
dp[i][j] = 1
if (j + 1) < m and dp[i][j + 1] == 1:
dp[i][j] = 1
if dp[0][0] == 0: return []
path = [(0, 0)]
while True:
(i, j) = path[-1]
if (i, j) == (n - 1, m - 1): break
if (i + 1) < n and dp[i + 1][j] == 1:
path.append((i + 1, j))
continue
if (j + 1) < m and dp[i][j + 1] == 1:
path.append((i, j + 1))
continue
return path
path = search()
# print(path)
if not path: return True
for x, y in path[1:-1]:
grid[x][y] = 0
# print(grid)
path = search()
if not path: return True
return False