/
disconnect-path-in-a-binary-matrix-by-at-most-one-flip.py
74 lines (67 loc) · 2.29 KB
/
disconnect-path-in-a-binary-matrix-by-at-most-one-flip.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
# Time: O(m * n)
# Space: O(m + n)
# dp
class Solution(object):
def isPossibleToCutPath(self, grid):
"""
:type grid: List[List[int]]
:rtype: bool
"""
for i in xrange(len(grid)):
for j in xrange(len(grid[0])):
if (i, j) == (0, 0) or grid[i][j] == 0:
continue
if (i-1 < 0 or grid[i-1][j] == 0) and (j-1 < 0 or grid[i][j-1] == 0):
grid[i][j] = 0
for i in reversed(xrange(len(grid))):
for j in reversed(xrange(len(grid[0]))):
if (i, j) == (len(grid)-1, len(grid[0])-1) or grid[i][j] == 0:
continue
if (i+1 >= len(grid) or grid[i+1][j] == 0) and (j+1 >= len(grid[0]) or grid[i][j+1] == 0):
grid[i][j] = 0
cnt = [0]*(len(grid)+len(grid[0])-1)
for i in xrange(len(grid)):
for j in xrange(len(grid[0])):
cnt[i+j] += grid[i][j]
return any(cnt[i] <= 1 for i in xrange(1, len(grid)+len(grid[0])-2))
# Time: O(m * n)
# Space: O(m + n)
# iterative dfs
class Solution2(object):
def isPossibleToCutPath(self, grid):
"""
:type grid: List[List[int]]
:rtype: bool
"""
def iter_dfs():
stk = [(0, 0)]
while stk:
i, j = stk.pop()
if not (i < len(grid) and j < len(grid[0]) and grid[i][j]):
continue
if (i, j) == (len(grid)-1, len(grid[0])-1):
return True
if (i, j) != (0, 0):
grid[i][j] = 0
stk.append((i, j+1))
stk.append((i+1, j))
return False
return not iter_dfs() or not iter_dfs()
# Time: O(m * n)
# Space: O(m + n)
# dfs
class Solution3(object):
def isPossibleToCutPath(self, grid):
"""
:type grid: List[List[int]]
:rtype: bool
"""
def dfs(i, j):
if not (i < len(grid) and j < len(grid[0]) and grid[i][j]):
return False
if (i, j) == (len(grid)-1, len(grid[0])-1):
return True
if (i, j) != (0, 0):
grid[i][j] = 0
return dfs(i+1, j) or dfs(i, j+1)
return not dfs(0, 0) or not dfs(0, 0)