Simulation volume leetcode [general] 1219 Golden Miner

Summary ： Simulation volume Leetcode Summary of questions

1219. Golden Miner

You're going to develop a gold mine , Geological surveyors have found out the distribution of resources in this gold mine , And use the size of  m * n The grid of grid It's marked . An integer in each cell represents the amount of gold in that cell ; If the cell is empty , So that is 0.

To maximize revenue , Miners need to mine gold according to the following rules ：

Every time a miner enters a unit , All the gold in that cell is collected .
Miners can walk up, down, left and right from their current position every time .
Each cell can only be mined （ Get into ） once .
No mining （ Get into ） The number of gold is 0 Cells of .
Miners can get out of the grid Any one Cells with gold start or stop .

Example 1：

Input ：grid = [[0,6,0],[5,8,7],[0,9,0]]
Output ：24
explain ：
[[0,6,0],
[5,8,7],
[0,9,0]]
One way to collect the most gold is ：9 -> 8 -> 7.
Example 2：

Input ：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output ：28
explain ：
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
One way to collect the most gold is ：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

Tips ：

1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
most 25 There's gold in one cell .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/path-with-maximum-gold
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

from leetcode_python.utils import *

class Solution:
    def __init__(self):
        self.res = 0

    @lru_cache(None)
    def next(self,rowid,colid):
        res = []
        for i, j in ((rowid - 1, colid), (rowid, colid - 1), (rowid + 1, colid), (rowid, colid + 1)):
            if 0 <= i < self.height and 0 <= j < self.width:
                res.append([i, j])
        return res

    def dfs(self,r,c,now):
        g = self.grid[r][c]
        now+=g
        self.res = max(self.res,now)
        self.grid[r][c]=0
        for nextr,nextc in self.next(r,c):
            if self.grid[nextr][nextc]:
                self.dfs(nextr,nextc,now)
        self.grid[r][c]=g

    def getMaximumGold(self, grid: List[List[int]]) -> int:
        self.grid = grid
        self.height,self.width = len(grid), len(grid[0])
        for i in range(self.height):
            for j in range(self.width):
                if grid[i][j]:
                    self.dfs(i,j,0)
        return self.res


def test(data_test):
    s = Solution()
    data = data_test  # normal
    # data = [list2node(data_test[0])] # list turn node
    return s.getMaximumGold(*data)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [
[[0,6,0],[5,8,7],[0,9,0]]],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！