Path with Maximum Gold

Patrick Leaton

Published: Nov. 13, 2021, 4:32 p.m.

Problem Description

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:

Every time you are located in a cell you will collect all the gold in that cell.
From your position, you can walk one step to the left, right, up, or down.
You can't visit the same cell more than once.
Never visit a cell with 0 gold.
You can start and stop collecting gold from any position in the grid that has some 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.length
n == grid[i].length
1 <= m, n <= 15
0 <= grid[i][j] <= 100
There are at most 25 cells containing gold.

The description was taken from https://leetcode.com/problems/path-with-maximum-gold/.

Problem Solution

#O(M*N(3^M*N)) Time, #O(M*N(3^M*N))  Space

class Solution:

    def getMaximumGold(self, grid: List[List[int]]) -> int:

        output = 0

        m, n = len(grid), len(grid[0])

        

        def in_bounds(row:int, col:int) -> bool:

            if row < 0 or col < 0 or row >= m or col >= n:

                return False

            if not grid[row][col]:

                return False

            return True

        

        def backtrack(row:int, col:int, path:int) -> None:

            nonlocal output

            if not in_bounds(row, col):

                return

            gold = grid[row][col]

            path += gold

            output = max(output, path)

            grid[row][col] = 0

            backtrack(row+1, col, path)

            backtrack(row-1, col, path)

            backtrack(row, col+1, path)

            backtrack(row, col-1, path)

            grid[row][col] = gold

        

        for row in range(m):

            for col in range(n):

                backtrack(row, col, 0)

        

        return output

Problem Explanation

If we had a defined source cell that we started the path from, like grid[0][0], then we could implement a version of Dijkstra's algorithm where we'd perform a Breadth-First Search through a max-heap that contains the gold value in each neighbor cell.

Since the source cell and the destination cell is undetermined, we have an overwhelming number of options.

Each cell in the grid will allow for a new possible source cell, so we are going to have to try each cell as a source cell and collect the maximum amount of gold for each of these paths.

To generate each of these paths, we can utilize backtracking.

Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function. This allows us to circulate elements into each valid position so that we can generate each valid combination.

A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, check if a placement is valid, then make the placement. Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.

In this problem, our placements would be marking a cell as zero to signify it has been seen, then reverting that marking after we have traversed every cell the cell has led to.

Let's start by initializing our output which will be the maximum path of gold, and also by saving the length and width of the grid to variables m, and n, so that we don't have to keep rewriting this later.

output = 0 m, n = len(grid), len(grid[0])

Next, we will make a helper function that will let us know if a cell is in bounds, this will let us know if a placement is valid.

def in_bounds(row:int, col:int) -> bool:

If the row or column is outside the bounds of the grid, or it contains zero gold, then we will return false.

if row < 0 or col < 0 or row >= m or col >= n: return False if not grid[row][col]: return False

Otherwise, we will return true.

return True

Next, we will make our backtrack function.

This function will take a row and column coordinate for the given cell, and also the gold amount for the given path up to that cell.

def backtrack(row:int, col:int, path:int) -> None:

Since our output variable is outside this given function, we will need to let Python know that it is nonlocal to this function.

nonlocal output

After, we will check if the given cell is valid by passing its coordinates to the helper function we just made.

If not, we will return from this path.

if not in_bounds(row, col): return

If the cell is valid, then we will create a temporary variable to save this cell's value, add that gold value to the path and check to see if this is the maximum gold so far.

gold = grid[row][col] path += gold output = max(output, path)

Once we do that, we will flip the gold value to zero so that we don't revisit it within this DFS path then continue the path down each bottom, top, right, and left neighbor.

grid[row][col] = 0 backtrack(row+1, col, path) backtrack(row-1, col, path) backtrack(row, col+1, path) backtrack(row, col-1, path)

When the DFS yoyo returns to the cell, we will backtrack by resetting its gold value.

This is so that we don't alter the baseline that future DFS paths will travel down.

grid[row][col] = gold

Now that our helper functions are built, we just need to generate each gold path by starting the backtrack function on each cell.

for row in range(m): for col in range(n): backtrack(row, col, 0)

After we have tried each path combination, we will return the maximum gold path that we encountered.

return output