In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.
Return the maximum amount of gold you can collect under the conditions:
0 gold.
Example 1:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]] Output: 24 Explanation: [[0,6,0], [5,8,7], [0,9,0]] Path to get the maximum gold, 9 -> 8 -> 7.
Example 2:
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]] Output: 28 Explanation: [[1,0,7], [2,0,6], [3,4,5], [0,3,0], [9,0,20]] Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 150 <= grid[i][j] <= 100This 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.
The C language implementation uses a recursive function 'dfs' to explore each valid path starting from a gold cell. It employs a grid to mark visited cells by setting their gold value to zero and restores them after backtracking is complete. This way, all potential paths can be explored to determine the path with the maximum gold.
C++
Java
Python
C#
JavaScript
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.
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.
This implementation uses a bitmask to track visited states and dynamic programming to store interim computations. It only traverses unvisited gold-bearing cells and optimizes path selection for maximal gold collection efficiency. State visits are held in a DP table indexed by the bitmask, with recursive exploration to uncover superior paths.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Backtracking with Depth-First Search | 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. |
| Dynamic Programming with Masking | 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. |
Google Coding Interview Question - Path With Maximum Gold (LeetCode) • AlgosWithMichael • 36,036 views views
Watch 9 more video solutions →Practice Path with Maximum Gold with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor