-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path1301_NumberPathsWithMaxScore.py
More file actions
163 lines (149 loc) · 14.1 KB
/
Copy path1301_NumberPathsWithMaxScore.py
File metadata and controls
163 lines (149 loc) · 14.1 KB
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
"""
You are given a square board of characters. You can move on the board starting at the bottom right square marked with
the character 'S'.
You need to reach the top left square marked with the character 'E'. The rest of the squares are labeled either with a
numeric character 1, 2, ..., 9 or with an obstacle 'X'. In one move you can go up, left or up-left (diagonally) only if
there is no obstacle there.
Return a list of two integers: the first integer is the maximum sum of numeric characters you can collect, and the
second is the number of such paths that you can take to get that maximum sum, taken modulo 10^9 + 7.
In case there is no path, return [0, 0].
"""
from typing import List
def paths_with_max_score(board: List[str]) -> List[int]:
n = len(board)
mod_value = 10 ** 9 + 7
invalid = (-n, 0)
# Reverse the traversal order, from E to S
dp_prev_row = [invalid] * n
for r in range(n):
dp_curr_row = []
for c in range(n):
if board[r][c] == 'E':
dp_curr_row.append((0, 1))
elif board[r][c] == 'X':
dp_curr_row.append(invalid)
else:
# move from up
curr_val, curr_step = dp_prev_row[c]
if c > 0:
# move from left
if dp_curr_row[-1][0] == curr_val:
curr_step += dp_curr_row[-1][1]
elif dp_curr_row[-1][0] > curr_val:
curr_val, curr_step = dp_curr_row[-1]
# move from up-left
if dp_prev_row[c - 1][0] == curr_val:
curr_step += dp_prev_row[c - 1][1]
elif dp_prev_row[c - 1][0] > curr_val:
curr_val, curr_step = dp_prev_row[c - 1]
curr_val += int(board[r][c]) if board[r][c] not in 'SE' else 0
curr_step %= mod_value
dp_curr_row.append((curr_val, curr_step))
dp_prev_row = dp_curr_row
return list(dp_prev_row[-1]) if dp_prev_row[-1][1] > 0 else [0, 0]
test_cases = [(["E23", "2X2", "12S"], [7, 1]),
(["E12", "1X1", "21S"], [4, 2]),
(["E11", "XXX", "11S"], [0, 0]),
(["E999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
"999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999S"],
[1773, 690285631]), ]
for test_board, expected_value in test_cases:
assert paths_with_max_score(test_board) == expected_value