Backtracking Target: 15s
Grid backtracking: visit cells with gold, mark visited by zeroing, restore on backtrack. Try every start.
def getMaximumGold(grid):
m, n = len(grid), len(grid[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
return 0
val = grid[i][j]
grid[i][j] = 0 # mark visited
best = 0
for di, dj in (0,1),(0,-1),(1,0),(-1,0):
best = max(best, dfs(i+di, j+dj))
grid[i][j] = val # unmark
return val + best
return max(dfs(i, j)
for i in range(m) for j in range(n)
if grid[i][j] > 0)Type it from memory. Go.