# 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 . The integer in each cell represents the yellow in this cell
# Gold quantity ; 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 .
#
# Related Topics Array to flash back matrix 118 0
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
max_gold = 0
def dfs(i, j, gold):
nonlocal max_gold
gold += grid[i][j]
rec = grid[i][j]
grid[i][j] = 0
max_gold = max(max_gold, gold)
for ni, nj in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):
if 0<=ni<m and 0<=nj<n and grid[ni][nj]>0:
dfs(ni, nj, gold)
grid[i][j] = rec # to flash back , Fill up the dug hole , Restore scene
return
for i in range(m):
for j in range(n):
if grid[i][j] > 0:
dfs(i, j, 0)
return max_gold
# leetcode submit region end(Prohibit modification and deletion)
