## 1219. Path with Maximum Gold

In a gold mine `grid` of size `m * 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:

• `1 <= grid.length, grid[i].length <= 15`
• `0 <= grid[i][j] <= 100`
• There are at most 25 cells containing gold.

## Rust Solution

``````struct Solution;

impl Solution {
fn get_maximum_gold(mut grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let m = grid[0].len();
let mut sum = 0;
let mut res = 0;
for i in 0..n {
for j in 0..m {
Self::dfs(i, j, &mut sum, &mut res, &mut grid, n, m);
}
}
res
}

fn dfs(
i: usize,
j: usize,
sum: &mut i32,
max: &mut i32,
grid: &mut Vec<Vec<i32>>,
n: usize,
m: usize,
) {
if grid[i][j] == 0 {
return;
}
let val = grid[i][j];
*sum += val;
*max = (*max).max(*sum);
grid[i][j] = 0;
if i > 0 {
Self::dfs(i - 1, j, sum, max, grid, n, m);
}
if j > 0 {
Self::dfs(i, j - 1, sum, max, grid, n, m);
}
if i + 1 < n {
Self::dfs(i + 1, j, sum, max, grid, n, m);
}
if j + 1 < m {
Self::dfs(i, j + 1, sum, max, grid, n, m);
}
grid[i][j] = val;
*sum -= grid[i][j];
}
}

#[test]
fn test() {
let grid = vec_vec_i32![[0, 6, 0], [5, 8, 7], [0, 9, 0]];
let res = 24;
assert_eq!(Solution::get_maximum_gold(grid), res);
let grid = vec_vec_i32![[1, 0, 7], [2, 0, 6], [3, 4, 5], [0, 3, 0], [9, 0, 20]];
let res = 28;
assert_eq!(Solution::get_maximum_gold(grid), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.