/
maximum-number-of-moves-in-a-grid.py
79 lines (74 loc) · 2.2 KB
/
maximum-number-of-moves-in-a-grid.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
75
76
77
78
79
# Time: O(m * n)
# Space: O(m)
# dp
class Solution(object):
def maxMoves(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
dp = [True]*len(grid)
result = 0
for c in xrange(len(grid[0])-1):
new_dp = [False]*len(grid)
for r in xrange(len(grid)):
if not dp[r]:
continue
if grid[r][c] < grid[r][c+1]:
new_dp[r] = True
if r-1 >= 0 and grid[r][c] < grid[r-1][c+1]:
new_dp[r-1] = True
if r+1 < len(grid) and grid[r][c] < grid[r+1][c+1]:
new_dp[r+1] = True
dp = new_dp
if not sum(dp):
break
else:
c = len(grid[0])-1
return c
# Time: O(m * n)
# Space: O(m)
# dp
class Solution2(object):
def maxMoves(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
dp = [0]*len(grid)
for c in reversed(xrange(len(grid[0])-1)):
new_dp = [0]*len(grid)
for r in xrange(len(grid)):
if grid[r][c] < grid[r][c+1]:
new_dp[r] = max(new_dp[r], dp[r]+1)
if r-1 >= 0 and grid[r][c] < grid[r-1][c+1]:
new_dp[r] = max(new_dp[r], dp[r-1]+1)
if r+1 < len(grid) and grid[r][c] < grid[r+1][c+1]:
new_dp[r] = max(new_dp[r], dp[r+1]+1)
dp = new_dp
return max(dp)
# Time: O(m * n)
# Space: O(m)
# bfs
class Solution3(object):
def maxMoves(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
q = set(xrange(len(grid)))
for c in xrange(len(grid[0])-1):
new_q = set()
for r in q:
if grid[r][c] < grid[r][c+1]:
new_q.add(r)
if r-1 >= 0 and grid[r][c] < grid[r-1][c+1]:
new_q.add(r-1)
if r+1 < len(grid) and grid[r][c] < grid[r+1][c+1]:
new_q.add(r+1)
q = new_q
if not q:
break
else:
c = len(grid[0])-1
return c