Maximum Gold Collectible Along a Non-Revisiting Path
Implement maxGoldCollected
You're given a grid where each cell holds some amount of gold (0 means none). Starting from any cell, moving to horizontally or vertically adjacent cells and never revisiting one already on the current path, find the maximum total gold collectible along any single path.
Tracking the current path as a list and scanning it to check for revisits is correct, but that scan gets more expensive the deeper the search goes — a path 10 steps long re-examines up to 10 entries just to place its 11th step. A boolean grid with one flag per cell answers the same "already on this path?" question in a single lookup, no matter how long the path has grown, while exploring the exact same set of possible paths.
Example 1:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Example 2:
Input: grid = [[1,1,1],[1,1,1],[1,1,1]]
Output: 9
Example 3:
Input: grid = [[0,0],[0,0]]
Output: 0
+ 4 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ grid.length, grid[0].length ≤ 6 - ●
0 ≤ grid[i][j] ≤ 50; a cell holding 0 has no gold and can never be stepped on - ●
A path may start at any cell, move to any horizontally or vertically adjacent cell, and never revisit a cell already on the current path
grid =
[[0,6,0], [5,8,7], [0,9,0]]