#2556

Disconnect Path in a Binary Matrix by at Most One Flip

expert · 1135 · lc medium +32 · verified · 27.8% accepted · 636 likes · top 6%

Description

In a 0-indexed m x n binary matrix grid, movement is only allowed to adjacent cells (down or right) with value 1. You may flip at most one cell (not the corners (0,0) or (m-1,n-1)). Return true if you can eliminate every path from (0, 0) to (m - 1, n - 1), otherwise return false.

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).

Code

1

2

3

class Solution:
    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:

class Solution:
    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool: