1219. Path with Maximum Gold

class Solution:
    # return max gold sum by starting at (sr, sc)
    def getMaxGoldFromCell(self, grid, sr, sc):
        originalValue = grid[sr][sc]
        bestByVisitingNeighbors = 0
        
        grid[sr][sc] = 0
        # explore neighbors
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            newR = sr + dy
            newC = sc + dx
            
            # Have to make sure that we are within the bounds
            if newR < 0 or newC < 0:
                continue
            if newR > len(grid) - 1 or newC > len(grid[0]) - 1:
                continue
            
            # At this point, we can access grid[newR][newC]
            if grid[newR][newC] == 0:
                continue
             
            # grid[newR][newC] IS A NON-0 element
            bestByVisitingNeighbors = max(bestByVisitingNeighbors, self.getMaxGoldFromCell(grid, newR, newC))
        grid[sr][sc] = originalValue
        
        return bestByVisitingNeighbors + originalValue
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        '''
        Input:
            grid - 2D grid of integers
                0 : Grid Empty
                1-100 : Amount of gold that you aquire.
        Output:
            Return max amount of gold by traversing a path that abides to the constraints.
        Constraints:
            You have to collect all gold in that cell.
            You can go up/down/left/right
            You cannot visit a cell twice.
            You cannot visit a cell with 0 gold. (wall)
            You can start and stop from anywhere.
        Example:
            [
                [0,6,0],
                [5,8,7],
                [0,9,0]
                
                6 -- 8 -- 5 -- x ==> 19
                6 -- 8 -- 7 --
                6 -- 8 -- 5/7/9 --
            ]
            You have to start at a non-0 cell.
            You end on a non-0 cell, You continue to explore paths as long as there is a non-0 cell
            that hasn't been visited.
        Approach:
            Backtracking.
            Keeping track of visited
                1. Maintain a 2D visited array.
                2. put (r,c) into a visitedSet. Then you can check if (r,c) in visitedSet.
                3. 
        
        '''
        maxVal = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                maxVal = max(maxVal, self.getMaxGoldFromCell(grid, r, c))
        return maxVal