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
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:
1 <= grid.length, grid[i].length <= 150 <= 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.