1219. Path with Maximum Gold

Partho Biswas · Partho Biswas · commit 52b3cf113fd9 · 2019-11-07T02:38:44.000+06:00
diff --git a/leetcode.com/python/1219_Path_with_Maximum_Gold.py b/leetcode.com/python/1219_Path_with_Maximum_Gold.py
@@ -0,0 +1,34 @@
+class Solution(object):
+    def getMaximumGold(self, grid):
+        """
+        :type grid: List[List[int]]
+        :rtype: int
+        """
+        totalGoldCollections = []
+        for rowIdx in range(len(grid)):
+            for colIdx in range(len(grid[0])):
+                if grid[rowIdx][colIdx] != 0:
+                    self.calculateGoldCollections(rowIdx, colIdx, 0, grid, totalGoldCollections)
+        return max(totalGoldCollections)
+
+    def calculateGoldCollections(self, rowIdx, colIdx, currentCollection, grid, totalGoldCollections):
+        if rowIdx < 0 or rowIdx >= len(grid) or colIdx < 0 or colIdx >= len(grid[0]) or grid[rowIdx][colIdx] == 0:
+            totalGoldCollections.append(currentCollection)
+            return  # Backtrack
+        currentCellGold = grid[rowIdx][colIdx]
+        grid[rowIdx][colIdx] = 0  # To prevent revisiting the cell
+        currentCollection += currentCellGold
+        self.calculateGoldCollections(rowIdx - 1, colIdx, currentCollection, grid,
+                                      totalGoldCollections)  # walk one step to the up
+        self.calculateGoldCollections(rowIdx, colIdx - 1, currentCollection, grid,
+                                      totalGoldCollections)  # walk one step to the left
+        self.calculateGoldCollections(rowIdx + 1, colIdx, currentCollection, grid,
+                                      totalGoldCollections)  # walk one step to the down
+        self.calculateGoldCollections(rowIdx, colIdx + 1, currentCollection, grid,
+                                      totalGoldCollections)  # walk one step to the right
+        grid[rowIdx][colIdx] = currentCellGold  # Restoring the grid
+        currentCollection -= currentCellGold  # recalculating collections
+
+
+
+
