Algorithm


Problem Name: 1219. Path with Maximum Gold

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.

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
  public int getMaximumGold(int[][] grid) {
    int maxGold = 0;
    int rows = grid.length;
    int cols = grid[0].length;
    for (int i = 0; i  <  rows; i++) {
      for (int j = 0; j  <  cols; j++) {
        int currGold = getMaxGold(grid, i, j, rows, cols, new boolean[rows][cols]);
        maxGold = Math.max(maxGold, currGold);
      }
    }
    return maxGold;
  }
  
  private int getMaxGold(int[][] grid, int x, int y, int rows, int cols, boolean[][] visited) {
    if (x  <  0 || x >= rows || y < 0 || y >= cols || visited[x][y] || grid[x][y] == 0) {
      return 0;
    }
    int curr = 0;
    visited[x][y] = true;
    for (int[] dir : dirs) {
      int newX = x + dir[0];
      int newY = y + dir[1];
      curr = Math.max(curr, getMaxGold(grid, newX, newY, rows, cols, visited));
    }
    visited[x][y] = false;
    return grid[x][y] + curr;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
grid = [[0,6,0],[5,8,7],[0,9,0]]

Output

x
+
cmd
24

#2 Code Example with Javascript Programming

Code - Javascript Programming


const getMaximumGold = function(grid) {
  const m = grid.length, n = grid[0].length
  const arr = []
  const dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
  const visited = new Set()
  for(let i = 0; i  <  m; i++) {
    for(let j = 0; j  <  n; j++) {
      if(grid[i][j] !== 0) arr.push([i, j])
    }
  }
  let res = 0
  
  for(const [i, j] of arr) {
    visited.clear()
    visited.add(`${i},${j}`)
    dfs(i, j, grid[i][j])
  }
  
  return res
  
  function dfs(i, j, cur) {

    res = Math.max(res, cur)
    for(const [dx, dy] of dirs) {
      const nx = i + dx
      const ny = j + dy
      const key = `${nx},${ny}`
      if(nx >= 0 && nx < m && ny >= 0 && ny < n && !visited.has(key) && grid[nx][ny] !== 0) {
        visited.add(key)
        dfs(nx, ny, cur + grid[nx][ny])
        visited.delete(key)
      }
    }
  }
  
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
grid = [[0,6,0],[5,8,7],[0,9,0]]

Output

x
+
cmd
24

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        def dfs(i, j, v):
            seen.add((i, j))
            dp[i][j] = max(dp[i][j], v)
            for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in seen:
                    dfs(x, y, v + grid[x][y])
            seen.discard((i, j))
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    seen = set()
                    dfs(i, j, grid[i][j])
        return max(c for row in dp for c in row)
Copy The Code & Try With Live Editor

Input

x
+
cmd
grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]

Output

x
+
cmd
28

#4 Code Example with C# Programming

Code - C# Programming


using System;

namespace LeetCode
{
    public class _1219_PathWithMaximumGold
    {
        public int GetMaximumGold(int[][] grid)
        {
            var count = 0;
            for (var i = 0; i  <  grid.Length; i++)
                for (var j = 0; j  <  grid[i].Length; j++)
                    if (grid[i][j] != 0) count = Math.Max(count, MaxGold(grid, i, j, 0));

            return count;
        }

        private int MaxGold(int[][] grid, int row, int col, int count)
        {
            if (row >= grid.Length || col >= grid[0].Length || row  <  0 || col < 0) return count;
            if (grid[row][col] == 0) return count;

            count += grid[row][col];

            var temp = grid[row][col];
            grid[row][col] = 0;

            var left = MaxGold(grid, row - 1, col, count);
            var right = MaxGold(grid, row + 1, col, count);
            var top = MaxGold(grid, row, col - 1, count);
            var bottom = MaxGold(grid, row, col + 1, count);
            grid[row][col] = temp;

            return Math.Max(Math.Max(left, right), Math.Max(top, bottom));
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]

Output

x
+
cmd
28
Advertisements

Demonstration


Previous
#1218 Leetcode Longest Arithmetic Subsequence of Given Difference Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1220 Leetcode Count Vowels Permutation Solution in C, C++, Java, JavaScript, Python, C# Leetcode