Walk over all grids without duplicate, with obstacles
Description
See LeetCode 980
DFS Backtracking Solution
Unlike the DP solutions to Unique path 1 and 2, we cannot reuse calculated paths cuz we can walk forth and back into the same arange (i, j). And the start and end position varies. Using a DFS.
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
|
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
n_row, n_col = len(grid), len(grid[0])
self.count, empty = 0, 1
# find start and end, count empty grids
for i in range(n_row):
for j in range(n_col):
if grid[i][j] == 0:
empty += 1
if grid[i][j] == 1:
start = [i, j]
if grid[i][j] == 2:
end = [i, j]
def search(i, j, empty):
if i in range(n_row) and j in range(n_col) and grid[i][j] >= 0:
if ([i, j] == end) and (empty == 0):
self.count += 1
return
grid[i][j] = -2
search(i-1, j, empty-1)
search(i+1, j, empty-1)
search(i, j-1, empty-1)
search(i, j+1, empty-1)
grid[i][j] = 0
search(start[0], start[1], empty)
return self.count
|
Note
- We initialize empty with 1, cuz the start of the search counts.
- Search in a grid is frequently used, we need to restore the element after search.
- The search function could be memorized to accelerate.