免费在线观看电视剧的网站,付费论坛源码,河池网络推广,top模板wordpress黄金矿工 leetcode1219. 黄金矿工题目描述回溯算法代码 回溯算法 leetcode1219. 黄金矿工 难度: 中等 eetcode 1219 黄金矿工 题目描述 你要开发一座金矿#xff0c;地质勘测学家已经探明了这座金矿中的资源分布#xff0c;并用大小为 m * n 的网格 grid 进行了标注。每个单元… 黄金矿工 leetcode1219. 黄金矿工题目描述回溯算法代码 回溯算法 leetcode1219. 黄金矿工 难度: 中等 eetcode 1219 黄金矿工 题目描述 你要开发一座金矿地质勘测学家已经探明了这座金矿中的资源分布并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量如果该单元格是空的那么就是 0。 为了使收益最大化矿工需要按以下规则来开采黄金 每当矿工进入一个单元就会收集该单元格中的所有黄金。 矿工每次可以从当前位置向上下左右四个方向走。 每个单元格只能被开采进入一次。 不得开采进入黄金数目为 0 的单元格。 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。 示例 1 输入grid [[0,6,0],[5,8,7],[0,9,0]] 输出24 解释 [[0,6,0], [5,8,7], [0,9,0]] 一种收集最多黄金的路线是9 - 8 - 7。 示例 2 输入grid [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]] 输出28 解释 [[1,0,7], [2,0,6], [3,4,5], [0,3,0], [9,0,20]] 一种收集最多黄金的路线是1 - 2 - 3 - 4 - 5 - 6 - 7。 提示 1 grid.length, grid[i].length 15 0 grid[i][j] 100 最多 25 个单元格中有黄金。 回溯算法 首先了解什么是回溯算法 解决一个回溯问题实际上就是一个决策树的遍历过程站在回溯树的一个节点上你只需要思考 3 个问题 路径也就是已经做出的选择。选择列表也就是你当前可以做的选择。结束条件也就是到达决策树底层无法再做选择的条件。
代码框架:
result []
def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择backtrack(路径, 选择列表)撤销选择 关于本体的解题思路: 我们首先在 m×nm \times nm×n 个网格内枚举起点。只要格子内的数大于 000它就可以作为起点进行开采。 记枚举的起点为 (i,j)我们就可以从 (i,j)开始进行递归 回溯枚举所有可行的开采路径。我们用递归函数 dfs(x,y,gold)\进行枚举其中 (x,y)(x, y)(x,y) 表示当前所在的位置gold\textit{gold}gold 表示在开采位置 (x,y)(x, y)(x,y) 之前已经拥有的黄金数量。根据题目的要求我们需要进行如下的步骤 我们需要将 gold 更新为 goldgrid[x][y]表示对位置(x,y) 进行开采。由于我们的目标是最大化收益因此我们还要维护一个最大的收益值 ans并在这一步使用 gold\textit{gold}gold 更新ans 我们需要枚举矿工下一步的方向。由于矿工每次可以从当前位置向上下左右四个方向走因此我们需要依次枚举每一个方向。如果往某一个方向不会走出网格并且走到的位置的值不为 0我们就可以进行递归搜索 在搜索完所有方向后我们进行回溯。 代码
class Solution {int[][]g;int m,n;//标记已经走过的路线boolean[][]vis;//标记四个方向,矿工每到一个地方,都有四个方向可以选择.int[][]dirs new int[][]{{1,0},{-1,0},{0,-1},{0,1}};public int getMaximumGold(int[][]gird){g gird;m g.length;n g[0].length;vis new boolean[m][n];int ans 0;for (int i 0; i m;i){for (int j 0; j n;j){if (g[i][j] ! 0){vis[i][j] true;ans Math.max(ans,dfs(i,j));vis[i][j] false;}}}return ans;}/*** 开始回溯计算,每个点向四个方向开始移动的最大值* param i* param j* return*/public int dfs(int i,int j){int ans g[i][j];//枚举四个方向for (int[]d : dirs){int ni i d[0];int nj j d[1];if (ni 0 || nj 0 || ni m || nj n){continue;}if (g[ni][nj] 0){continue;}//已经走过的不在重复计算if (vis[ni][nj]){continue;}//标记已选vis[ni][nj] true;ans Math.max(ans,g[i][j] dfs(ni,nj));vis[ni][nj] false;}return ans;}
}回溯算法
leetcode698. 划分为k个相等的子集
leetcode93. 复原 IP 地址
leetcode306. 累加数
