You are given a 0-indexed m x n binary matrix grid. You can move from a cell (row, col) to any of the cells (row + 1, col) or (row, col + 1) that has the value 1. The matrix is disconnected if there is no path from (0, 0) to (m - 1, n - 1).
You can flip the value of at most one (possibly none) cell. You cannot flip the cells (0, 0) and (m - 1, n - 1).
Return true if it is possible to make the matrix disconnect or false otherwise.
Note that flipping a cell changes its value from 0 to 1 or from 1 to 0.
Example 1:
Input: grid = [[1,1,1],[1,0,0],[1,1,1]] Output: true Explanation: We can change the cell shown in the diagram above. There is no path from (0, 0) to (2, 2) in the resulting grid.
Example 2:
Input: grid = [[1,1,1],[1,0,1],[1,1,1]] Output: false Explanation: It is not possible to change at most one cell such that there is not path from (0, 0) to (2, 2).
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10001 <= m * n <= 105grid[i][j] is either 0 or 1.grid[0][0] == grid[m - 1][n - 1] == 1Perform a BFS or DFS from the starting point (0, 0) to determine if there is a path to (m-1, n-1). Record reachable cells. If these cells all remain connected even after a potential flip, then the grid cannot be disconnected. Otherwise, assess if flipping a single cell can break the connection.
The function uses a BFS to check if the grid is initially connected from (0, 0) to (m-1, n-1). If it is connected, the code then explores flipping each 0 cell adjacent to the connected path to determine if the grid can be disconnected by such a flip.
JavaScript
Identify critical cells that are necessary for maintaining a path from (0, 0) to (m-1, n-1). Implement union-find to manage connectivity dynamically, and then flip cells to test disconnection potential while keeping track of reachability separately.
This C++ solution introduces a function to assess path existence via BFS, and tries flipping all 0s to check disconnection result. The logic is parallel to the BFS approach deconstructed earlier but refactored into modular functions suitable for C++ patterns.
Java
| Approach | Complexity |
|---|---|
| BFS/DFS to Check Initial Connectivity |
|
| Track Reachable and Critical Cells Separately |
|
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,679 views views
Watch 9 more video solutions →Practice Disconnect Path in a Binary Matrix by at Most One Flip with our built-in code editor and test cases.
Practice on FleetCode