Path with maximum gold

Array Backtracking Matrix

68.3% acceptance

Feb 25, 2026

3431

105

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_maximum_gold(mut grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut ans = 0;

    fn dfs(grid: &mut Vec<Vec<i32>>, r: usize, c: usize, m: usize, n: usize) -> i32 {
      let val = grid[r][c];
      grid[r][c] = 0;
      let mut best = 0;
      let dirs: [(i32, i32); 4] = [(-1,0),(1,0),(0,-1),(0,1)];
      for (dr, dc) in dirs {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr >= 0 && nr < m as i32 && nc >= 0 && nc < n as i32 && grid[nr as usize][nc as usize] > 0 {
          best = best.max(dfs(grid, nr as usize, nc as usize, m, n));
        }
      }
      grid[r][c] = val;
      val + best
    }

    for i in 0..m {
      for j in 0..n {
        if grid[i][j] > 0 {
          ans = ans.max(dfs(&mut grid, i, j, m, n));
        }
      }
    }
    ans
  }
}