-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathshortest-path-in-a-grid-with-obstacles-elimination.py
217 lines (206 loc) · 8.93 KB
/
shortest-path-in-a-grid-with-obstacles-elimination.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
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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
# 1293. Shortest Path in a Grid with Obstacles Elimination
# 🔴 Hard
#
# https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
#
# Tags: Array - Breadth-First Search - Matrix
import timeit
from collections import deque
from heapq import heappop, heappush
from typing import List
# Use BFS to visit cells in the grid keeping track of combinations of
# row/col/removals that we have seen already.
#
# Time complexity: O(m*n*k) - We may visit each combination of row,
# column and number of removals before we find a solution or decide that
# there isn't one.
# Space complexity: O(m*n*k) - Both the visited set and the queue will
# grow linearly in size with the size of the input.
#
# Runtime: 79 ms, faster than 95.42%
# Memory Usage: 15.3 MB, less than 76.48%
class BFS:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
NUM_ROWS, NUM_COLS = len(grid), len(grid[0])
# If k is big enough, ignore the obstacles.
if k > (NUM_ROWS - 1 + NUM_COLS - 1):
return NUM_ROWS - 1 + NUM_COLS - 1
# Use a queue of (distance traveled, removals used, row, col)
q = deque([(0, 0, 0, 0)])
# The four directions we travel to get to the neighbors.
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
# Store combinations that we have pushed into the heap already.
seen = {(0, 0, 0, 0)}
while q:
moves, rem, row, col = q.popleft()
for x, y in dirs:
# Get the neighbor's cell row and column.
n_row, n_col = row + x, col + y
# If the cell is within bounds.
if 0 <= n_row < NUM_ROWS and 0 <= n_col < NUM_COLS:
dist = moves + 1
# If the cell is not an obstacle.
if not grid[n_row][n_col]:
q_item = (dist, rem, n_row, n_col)
set_item = (rem, n_row, n_col)
if set_item not in seen:
if n_row == NUM_ROWS - 1 and n_col == NUM_COLS - 1:
return dist
q.append(q_item)
seen.add(set_item)
elif rem < k:
q_item = (dist, rem + 1, n_row, n_col)
set_item = (rem + 1, n_row, n_col)
if set_item not in seen:
q.append(q_item)
seen.add(set_item)
# We could not reach the target.
return -1
# Use a modified version of Dijkstra where we push into the heap current
# distance traveled plus the number of obstacles removed. We also keep
# track of the best time to get to a cell for each of the possible
# values of k. This is not an optimization over the BFS solution because
# we cannot greedily keep the shortest travel time to a cell without
# taking into account the number of obstacles that we have removed. I am
# keeping this solution here because it was the first one I came up with
# and it passes the tests.
#
# Time complexity: O(m*n*k*log(m*n*k)) - We may visit each combination
# of row/col/removals once, for each, we may push and pop from the heap.
# Space complexity: O(m*n*k) - Both the heap and the dp object can grow
# to that size.
#
# Runtime: 162 ms, faster than 74.62%
# Memory Usage: 19.9 MB, less than 43.79%
class Dijkstra:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
NUM_ROWS, NUM_COLS = len(grid), len(grid[0])
# If k is big enough, ignore the obstacles.
if k > (NUM_ROWS - 1 + NUM_COLS - 1):
return NUM_ROWS - 1 + NUM_COLS - 1
# Use a heap of (distance traveled, removals used, row, col)
heap = [(0, 0, 0, 0)]
# Use a grid of m*n*k size to store the best time to get to each
# cell while still having k removals.
dp = [
[[float("inf") for _ in range(k + 1)] for _ in range(NUM_COLS)]
for _ in range(NUM_ROWS)
]
dp[0][0] = [0] * (k + 1)
# The four directions we travel to get to the neighbors.
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
# Store combinations that we have pushed into the heap already.
seen = {(0, 0, 0, 0)}
# Process positions on the heap while there are still any.
while heap:
# removals done, moves taken, row, col
moves, rem, row, col = heappop(heap)
for x, y in dirs:
# Get the neighbor's cell row and column.
n_row, n_col = row + x, col + y
# If the cell is within bounds.
if 0 <= n_row < NUM_ROWS and 0 <= n_col < NUM_COLS:
dist = moves + 1
# If the cell is not an obstacle.
if not grid[n_row][n_col]:
# If this distance is better that the previous
# best with this number of removals, update it.
comb = (dist, rem, n_row, n_col)
if dist < dp[n_row][n_col][rem] and comb not in seen:
if n_row == NUM_ROWS - 1 and n_col == NUM_COLS - 1:
return dist
dp[n_row][n_col][rem] = dist
# If we update the value, we want to
# reprocess travel from this cell.
heappush(heap, comb)
seen.add(comb)
# If the neighbor is an obstacle and we have
# removals left on this branch. If we don't have any
# removals left, this branch dies.
elif rem < k:
comb = (dist, rem + 1, n_row, n_col)
if comb not in seen:
dp[n_row][n_col][rem + 1] = dist
heappush(heap, comb)
seen.add(comb)
# We have traveled all possible paths and could not find a way
# to reach the target cell.
return -1
def test():
executors = [
BFS,
Dijkstra,
]
tests = [
[[[0, 1, 1], [1, 1, 1], [1, 0, 0]], 1, -1],
[[[0, 0, 0], [1, 1, 0], [0, 0, 0], [0, 1, 1], [0, 0, 0]], 1, 6],
[
[
[0, 0, 1, 0, 1, 1, 1, 0],
[1, 1, 0, 1, 0, 1, 0, 0],
[1, 1, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 0, 1, 0, 0],
[1, 0, 0, 1, 0, 1, 0, 1],
[0, 0, 1, 1, 1, 0, 0, 1],
[0, 1, 0, 1, 1, 1, 1, 0],
[1, 0, 0, 0, 1, 1, 1, 0],
[0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0],
[1, 0, 1, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 0, 1],
[0, 0, 1, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 1],
[1, 1, 0, 0, 1, 0, 0, 0],
[0, 1, 1, 1, 0, 0, 1, 1],
[0, 1, 0, 0, 0, 0, 1, 0],
[1, 1, 1, 0, 1, 0, 0, 0],
[1, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 0, 1, 0, 0, 1, 0],
[1, 1, 1, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 1, 1],
[0, 1, 0, 0, 0, 0, 1, 1],
[1, 1, 1, 0, 0, 0, 1, 1],
[0, 1, 0, 0, 1, 0, 0, 1],
[1, 0, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 1, 0, 1, 0],
],
3,
-1,
],
[
[
[0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1],
[0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0],
[1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1],
[1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0],
],
27,
24,
],
]
for executor in executors:
start = timeit.default_timer()
for _ in range(1):
for col, t in enumerate(tests):
sol = executor()
result = sol.shortestPath(t[0], t[1])
exp = t[2]
assert result == exp, (
f"\033[93m» {result} <> {exp}\033[91m for"
+ f" test {col} using \033[1m{executor.__name__}"
)
stop = timeit.default_timer()
used = str(round(stop - start, 5))
cols = "{0:20}{1:10}{2:10}"
res = cols.format(executor.__name__, used, "seconds")
print(f"\033[92m» {res}\033[0m")
test()