This is the 22nd day of my participation in the August Wen Challenge.More challenges in August

describe

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: the grid = [,6,0 [0], [5,8,7], [0,9,0]] Output: 24 Explanation: 5,8,7,6,0 [[0], [], [0,9,0]] the Path to get the maximum gold, 9 - > 8 - > 7.Copy the code

Example 2:

Input: the grid = [,0,7 [1], [2,0,6], [three, four, five], [0,3,0], [9,0,20]] Output: 28 Explanation: ,0,6,0,7 [[1], [2], [three, four, five], [0,3,0], [9,0,20]] the Path to get the maximum gold, 1 - > 2 - > 3 - > 4 - > 5 - > 6 - > 7.Copy the code

Note:

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

parsing

Each grid[I][j] has a number representing the amount of gold. Now you are a gold digger. You can start at any position in the gold matrix and go up, down, left, or right. But you can’t visit the location where the gold number is 0 and at the same time you can’t walk through the location to find the maximum amount of gold you can get.

Use the set “used” to record the position that the gold has passed through. Start from the position where all gold is not 0 to get the maximum amount of gold that can be obtained, record it in DP, and then find the maximum number from DP, that is, the answer.

answer

class Solution(object):
    def getMaximumGold(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])

        def countGold(gold, i, j):
            used.add((i, j))
            dp[i][j] = max(dp[i][j], gold)
            for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in used:
                    countGold(gold + grid[x][y], x, y)
            used.discard((i, j))

        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                used = set()
                if grid[i][j]:
                    countGold(grid[i][j], i, j)
        return max(c for row in dp for c in row)
        	      
		
Copy the code

The results

Given in the Python online submission with Maximum Gold. Memory Usage: 10000 ms Submissions in Python online submissions for Path with Maximum Gold.Copy the code

Original link: leetcode.com/problems/pa…

Your support is my biggest motivation