Sponsored
Sponsored
This approach utilizes backtracking and depth-first search (DFS) to explore all possible paths to collect the maximum gold. Start from each cell containing gold and perform DFS to explore in all four possible directions (up, down, left, right). During the search, keep track of the total gold collected. Use backtracking to unvisit a cell after exploring all potential paths from it.
Time complexity: O((m*n)^2) - In the worst-case scenario, each cell containing gold gets visited and backtracked.
Space complexity: O(m*n) - This results from recursive stack space and the grid modifications.
The Python solution adopts a recursive depth-first search enabled by the dfs function. It systematically explores all avenues for gold collection, marking visited cells and backtracking to restore prior states when necessary. The recursive depth and methodical plotting ensure complete path examination.
This approach involves using dynamic programming with bit masking to track visited states and optimize the path of maximum gold collection. It systematically calculates the maximum gold that can be gathered by starting from each gold cell and considering valid moves while ensuring no cell is revisited.
Time complexity: O(2^(m*n) * m * n) given bitmask state examination.
Space complexity: O(2^(m*n) * m * n) due to DP storage needs for various path states.
1class Solution:
2 def getMaximumGold(self, grid):
3 import functools
4
5 @functools.lru_cache(None)
6 def dp(mask, x, y):
7 maxGold = 0
8 for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
9 nx, ny = x + dx, y + dy
10 if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] > 0:
11 bit = 1 << (nx * len(grid[0]) + ny)
12 if not (mask & bit):
13 maxGold = max(maxGold, dp(mask | bit, nx, ny))
14 return grid[x][y] + maxGold
15
16 maxGold = 0
17 for i in range(len(grid)):
18 for j in range(len(grid[0])):
19 if grid[i][j] > 0:
20 bit = 1 << (i * len(grid[0]) + j)
21 maxGold = max(maxGold, dp(bit, i, j))
22 return maxGoldThe Python algorithm employs @functools.lru_cache to optimize the DP process, significantly reducing computation time through memoization techniques. This permits efficient path resolution by retaining repetitive calculations, yielding improved performance despite potential combinatorial explosion from bitmask exploration.