DEV Community

Cover image for 1219. Path with Maximum Gold
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Updated on

1219. Path with Maximum Gold

1219. Path with Maximum Gold

Medium

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.

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:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 15
  • 0 <= grid[i][j] <= 100
  • There are at most 25 cells containing gold.

Solution:

class Solution {

    /**
     * @param Integer[][] $grid
     * @return Integer
     */
    function getMaximumGold($grid) {
        $m = count($grid);
        $n = count($grid[0]);

        $dfs = function ($i, $j) use (&$dfs, $m, $n, &$grid) {
            if ($i < 0 || $i >= $m || $j < 0 || $j >= $n || !$grid[$i][$j]) {
                return 0;
            }
            $v = $grid[$i][$j];
            $grid[$i][$j] = 0;
            $ans = $v + max([$dfs($i - 1, $j), $dfs($i + 1, $j), $dfs($i, $j - 1), $dfs($i, $j + 1)]);
            $grid[$i][$j] = $v;
            return $ans;
        };

        $ans = 0;
        for ($i = 0; $i < $m; ++$i) {
            for ($j = 0; $j < $n; ++$j) {
                $ans = max($ans, $dfs($i, $j));
            }
        }

        return $ans;
    }
}
Enter fullscreen mode Exit fullscreen mode

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

Top comments (0)