黄金矿工 回溯法"/>
黄金矿工 回溯法
黄金矿工
你要开发一座金矿,地质勘测学家已经探明了这座金矿中的资源分布,并用大小为 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
更多推荐
黄金矿工 回溯法
发布评论