Algorithm
Problem Name: 1219. Path with Maximum Gold
Problem Link: https://leetcode.com/problems/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
0gold. - 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.lengthn == grid[i].length1 <= m, n <= 150 <= 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;
}
}
Input
grid = [[0,6,0],[5,8,7],[0,9,0]]
Output
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)
}
}
}
};
Input
grid = [[0,6,0],[5,8,7],[0,9,0]]
Output
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)
Input
grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output
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));
}
}
}
Input
grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output
28