1219. Path with Maximum Gold

[jason89521]

Practice Dates

• 2024/05/15

Description

Link: https://leetcode.com/problems/path-with-maximum-gold/description/

Solution

Use a recursive function to compare all paths and find the maximum value.

use std::cmp;

impl Solution {
    pub fn get_maximum_gold( mut grid: Vec<Vec<i32>>) -> i32 {
        let mut max = 0;
        let row_len = grid.len();
        let col_len = grid[0].len();
        for row in 0..row_len {
            for col in 0..col_len {
                max = cmp::max(max, Self::find_max(&mut grid, row, col, row_len, col_len));
            }
        }

        return max;
    }

    fn find_max(grid: &mut Vec<Vec<i32>>, row: usize, col: usize, row_len: usize, col_len: usize) -> i32 {
        if row < 0 || row >= row_len || col < 0 || col >= col_len || grid[row][col] == 0 {
            return 0;
        }

        let origin = grid[row][col];
        grid[row][col] = 0;
        let mut max = 0;
        max = cmp::max(max, Self::find_max(grid, row-1, col, row_len, col_len));
        max = cmp::max(max, Self::find_max(grid, row+1, col, row_len, col_len));
        max = cmp::max(max, Self::find_max(grid, row, col-1, row_len, col_len));
        max = cmp::max(max, Self::find_max(grid, row, col+1, row_len, col_len));
        grid[row][col] = origin;

        return origin + max;
    }

}

Performance

Time complexity: