黄金矿工 回溯法

黄金矿工 回溯法"/>

黄金矿工 回溯法

黄金矿工

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

为了使收益最大化，矿工需要按以下规则来开采黄金：

每当矿工进入一个单元，就会收集该单元格中的所有黄金。
矿工每次可以从当前位置向上下左右四个方向走。
每个单元格只能被开采（进入）一次。
不得开采（进入）黄金数目为 0 的单元格。
矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

回溯法+dfs

class Solution:def getMaximumGold(self, grid: List[List[int]]) -> int:def dfs(i,j):   #深度优先搜索if i<0 or j<0 or i>=m or j>=n or grid[i][j]==0: #超出矩阵范围或已被访问或本来就不能访问return 0temp=grid[i][j]grid[i][j]=0  #作为本轮起点已被访问res=0for ii, jj in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):res = max(res,dfs(ii,jj))   #找到四个方向的最大值grid[i][j]=temp    #恢复return res+grid[i][j]  #返回四个方向的最大值加上本轮起点m,n=len(grid),len(grid[0])num_max = 0for i in range(m):for j in range(n):if grid[i][j]!=0:  #遍历每一个不为0的数作为起点# visited=[[0]*n for _ in range(m)]  #也可以另外设置矩阵记录每轮已被访问的位置num_max = max(num_max,dfs(i,j))return num_max

另外设置visited矩阵的写法

class Solution:def getMaximumGold(self, grid: List[List[int]]) -> int:def dfs(i,j):   #深度优先搜索if i<0 or j<0 or i>=m or j>=n or grid[i][j]==0 or visited[i][j]==0: #超出矩阵范围或已被访问或本来就不能访问return 0# temp=grid[i][j]# grid[i][j]=0  #作为本轮起点已被访问visited[i][j]=0res=0for ii, jj in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):res = max(res,dfs(ii,jj))   #找到四个方向的最大值# grid[i][j]=temp    #恢复visited[i][j]=1return res+grid[i][j]  #返回四个方向的最大值加上本轮起点m,n=len(grid),len(grid[0])num_max = 0visited=[[1]*n for _ in range(m)]  #也可以另外设置矩阵记录每轮已被访问的位置for i in range(m):for j in range(n):if grid[i][j]!=0:  #遍历每一个不为0的数作为起点num_max = max(num_max,dfs(i,j))return num_max