1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// @Title: 黄金矿工 (Path with Maximum Gold)
// @Author: 15816537946@163.com
// @Date: 2022-02-06 18:18:52
// @Runtime: 8 ms
// @Memory: 2.1 MB
// struct Solution;
impl Solution {
    pub fn get_maximum_gold(mut grid: Vec<Vec<i32>>) -> i32 {
        fn dfs((i, j): (usize, usize), gold: i32, ans: &mut i32, grid: &mut Vec<Vec<i32>>) {
            let cur = grid[i][j];
            *ans = (*ans).max(gold + cur);
            grid[i][j] = 0;

            for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)] {
                if x < grid.len() && y < grid[0].len() && grid[x][y] > 0 {
                    dfs((x, y), gold + cur, ans, grid);
                }
            }

            grid[i][j] = cur;
        }

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

        ans
    }
}