Class Solution
java.lang.Object
g2501_2600.s2556_disconnect_path_in_a_binary_matrix_by_at_most_one_flip.Solution
2556 - Disconnect Path in a Binary Matrix by at Most One Flip.<p>Medium</p>
<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>. 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><strong>Example 1:</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2022/12/07/yetgrid2drawio.png" alt="" /></p>
<p><strong>Input:</strong> grid = [[1,1,1],[1,0,0],[1,1,1]]</p>
<p><strong>Output:</strong> true</p>
<p><strong>Explanation:</strong></p>
<p>We can change the cell shown in the diagram above. There is no path from (0, 0) to (2, 2) in the resulting grid.</p>
<p><strong>Example 2:</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2022/12/07/yetgrid3drawio.png" alt="" /></p>
<p><strong>Input:</strong> grid = [[1,1,1],[1,0,1],[1,1,1]]</p>
<p><strong>Output:</strong> false</p>
<p><strong>Explanation:</strong></p>
<p>It is not possible to change at most one cell such that there is not path from (0, 0) to (2, 2).</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 <= m, n <= 1000</code></li>
<li><code>1 <= m * n <= 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>
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
Solution
public Solution()
-
-
Method Details
-
isPossibleToCutPath
public boolean isPossibleToCutPath(int[][] g)
-