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
}
}
|