LC 0980 [H] Unique Paths III - ALawliet/algorithms GitHub Wiki
DFS because we need to visit all the cells, backtrack because we need to mark them visited and then undo it for each iteration of the 4 directions
class Solution:
def uniquePathsIII(self, A):
self.count = 0
ROWS = len(A)
COLS = len(A[0])
start_r = None
start_c = None
num_empty = 1 # include start
# count empty, the
for r in range(ROWS):
for c in range(COLS):
if A[r][c] == 1: # find starting square
start_r, start_c = (r, c)
elif A[r][c] == 0: # count rest of walkable squares
num_empty += 1
def dfs(r, c, num_remain):
if not ( (0 <= r < ROWS and 0 <= c < COLS) and (A[r][c] >= 0) ): return # (in bounds) and (walkable=0 or start=1 or end=2)
# not (A[r][c] < 0) # obstacle=-1 or visited=-2
if A[r][c] == 2: # ending square
if num_remain == 0:
self.count += 1
else:
A[r][c] = -2 # mark visited for next direction
for dr, dc in ((0,1),(0,-1),(1,0),(-1,0)):
dfs(r + dr, c + dc, num_remain - 1)
A[r][c] = 0 # recursion done, backtrack
dfs(start_r, start_c, num_empty)
return self.count