#1219
Path with Maximum Gold
pupil · 580 · lc medium +29 · verified · 68.3% accepted · 3,432 likes · top 75%
Description
You are given an m x n grid where each cell holds a non-negative integer representing gold (0 means empty).
Starting from any non-empty cell, navigate through adjacent (up, down, left, right) non-empty cells without revisiting any cell. Collect all gold in every visited cell.
Return the maximum total gold collectable. You may begin and end at any non-empty cell.
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.
Code
1
2
3