## 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 &

Input

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

Output

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()
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) {
dfs(nx, ny, cur + grid[nx][ny])
visited.delete(key)
}
}
}

};
``````
Copy The Code &

Input

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

Output

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):
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])
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 &

Input

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

Output

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 &

Input

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

Output

cmd
28