LeetCode 题解工作台
二进制矩阵中翻转最多一次使路径不连通
给你一个下标从 0 开始的 m x n 二进制 矩阵 grid 。你可以从一个格子 (row, col) 移动到格子 (row + 1, col) 或者 (row, col + 1) ，前提是前往的格子值为 1 。如果从 (0, 0) 到 (m - 1, n - 1) 没有任何路径，我们称该矩阵是 …
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们先进行一次 DFS，判断从 $(0, 0)$ 到 $(m - 1, n - 1)$ 是否存在路径，记结果为 。在 DFS 的过程中，我们将访问过的格子的值置为 ，以防止重复访问。 接下来，我们将 $(0, 0)$ 和 $(m - 1, n - 1)$ 的值置为 ，再进行一次 DFS，判断从 $(0, 0)$ 到 $(m - 1, n - 1)$ 是否存在路径，记结果为 。在 DFS 的过程中，…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个下标从 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
解题思路
方法一：两次 DFS
我们先进行一次 DFS，判断从 到 是否存在路径，记结果为 。在 DFS 的过程中，我们将访问过的格子的值置为 ，以防止重复访问。
接下来，我们将 和 的值置为 ，再进行一次 DFS，判断从 到 是否存在路径，记结果为 。在 DFS 的过程中，我们将访问过的格子的值置为 ，避免重复访问。
最后，如果 和 都为 true，则返回 false，否则返回 true。
时间复杂度 ，空间复杂度 。其中 和 分别是矩阵的行数和列数。
class Solution:
def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
def dfs(i, j):
if i >= m or j >= n or grid[i][j] == 0:
return False
grid[i][j] = 0
if i == m - 1 and j == n - 1:
return True
return dfs(i + 1, j) or dfs(i, j + 1)
m, n = len(grid), len(grid[0])
a = dfs(0, 0)
grid[0][0] = grid[-1][-1] = 1
b = dfs(0, 0)
return not (a and b)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on performing two full traversals of the grid for reachability, plus iterating over potential critical cells, yielding roughly O(m * n). Space complexity is O(m * n) for the DP tables and recursion/queue structures. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask about handling large grids efficiently using DP instead of exhaustive path enumeration.
- question_mark
Probe knowledge of critical path identification in state transition DP for matrices.
- question_mark
Check understanding of combining forward and backward traversal for minimal flips.
常见陷阱
外企场景- error
Forgetting to exclude the top-left and bottom-right cells from possible flips.
- error
Failing to identify cells that are truly critical to all paths, leading to incorrect disconnection checks.
- error
Using BFS/DFS without DP may result in excessive time complexity for large grids.
进阶变体
外企场景- arrow_right_alt
Allow flipping multiple cells and determine the minimum number needed to disconnect the path.
- arrow_right_alt
Consider diagonal moves along with right and down for more complex connectivity.
- arrow_right_alt
Determine the maximum number of disjoint paths that remain after one flip.