一.题目1219. 黄金矿工 - 力扣LeetCode二.思路讲解2.1 审题本题要求在一个网格中开采黄金每个单元格有黄金数量非零的格子才能进入从任意有黄金的格子出发可以上下左右移动每个格子只能进入一次收集的黄金数量等于经过格子的黄金之和目标是最大化收集的黄金总量。本质是寻找一条不重复访问非零格子的路径使路径上黄金总和最大。2.2 思路讲解本题与单词搜索的思路完全一致都是回溯DFS只是目标从“匹配单词”变成了“求和最大”。我们可以遍历所有非零格子作为起点从起点出发进行深度优先搜索每次向四个方向探索并记录当前路径的黄金总和。回溯恢复现场每进入一个格子将其标记为已访问递归返回后取消标记以便其他路径使用。剪枝只有格子未被访问且黄金非零时才进入。更新最大值每次到达一个无法继续的位置或递归过程中时用当前路径和更新全局最大值。无需考虑起点选择因为所有非零格子都可能作为起点遍历所有即可。三.代码演示class Solution { public: bool check[16][16]; int row,col; int ret 0;//最终的结果 int getMaximumGold(vectorvectorint grid) { row grid.size(),col grid[0].size(); for(int i 0;i row;i) { for(int j 0;j col;j) { //判断这个是不是能走的格子 if(grid[i][j] ! 0) { check[i][j] true; dfs(grid,i,j,grid[i][j]); //恢复 check[i][j] false; } } } return ret; } int dx[4] {0,0,1,-1}; int dy[4] {1,-1,0,0}; void dfs(vectorvectorint grid,int i,int j,int path) { ret max(ret,path); for(int k 0;k 4;k) { int x i dx[k],y j dy[k]; if(x 0 y 0 x row y col !check[x][y] grid[x][y] ! 0) { check[x][y] true; dfs(grid,x,y,path grid[x][y]); check[x][y] false; } } } };四.代码讲解一、全局变量与数据结构check[16][16]布尔数组记录每个格子是否已被当前路径访问过。题目网格最大为 15×15大小 16 足够。row、col成员变量存储网格的行数和列数。ret整型变量记录当前找到的最大黄金收集量初始为 0。方向数组dx[4]、dy[4]表示上下左右四个方向的偏移量方便探索相邻格子。二、主函数getMaximumGold获取网格的行数row和列数col并赋值给成员变量。遍历整个网格如果某个格子上的黄金数量不为 0则以此格子作为起点开始搜索将该格子标记为已访问check[i][j] true。调用递归函数dfs从该格子出发当前路径黄金总和初始为grid[i][j]。递归返回后恢复现场将该格子标记为未访问check[i][j] false以便其他起点或分支能够使用。遍历完所有起点后返回全局最大值ret。三、递归函数dfsdfs(grid, i, j, path)表示当前位于格子(i, j)已收集的黄金总量为path。执行流程如下1. 更新最大值每进入一个格子首先用当前路径和path更新全局最大值ret因为可能在此处停止。注意即使还能继续走也要先记录当前值因为可以在任意位置停止。2. 向四个方向探索使用for循环遍历四个方向计算新坐标(x, y)。对于每个方向检查该格子是否合法边界检查x 0 y 0 x row y col。未访问!check[x][y]。有黄金grid[x][y] ! 0。如果三个条件都满足则将(x, y)标记为已访问check[x][y] true。递归调用dfs(grid, x, y, path grid[x][y])继续收集黄金。递归返回后回溯将(x, y)标记为未访问check[x][y] false以便尝试其他方向或路径。3. 递归终止当四个方向都探索完该层递归自然结束返回上一层。无需额外终止条件因为ret已在进入时更新。四、回溯与恢复现场回溯是本题的核心。当从当前格子出发的某条路径探索完毕时必须将当前格子标记恢复为未访问否则其他路径将无法经过此格子导致漏解。这正是通过check[x][y] false实现的。五、关键细节起点选择遍历所有非零格子作为起点因为黄金矿工可以从任意有黄金的格子出发。方向顺序上下左右四个方向无顺序要求任何顺序均可。路径长度的记录在每次进入格子后立即更新最大值因为可以在任意位置停止无需等到无路可走。剪枝通过check数组和grid[x][y] ! 0条件避免了无效的移动。
深搜练习(黄金矿工)(13)
一.题目1219. 黄金矿工 - 力扣LeetCode二.思路讲解2.1 审题本题要求在一个网格中开采黄金每个单元格有黄金数量非零的格子才能进入从任意有黄金的格子出发可以上下左右移动每个格子只能进入一次收集的黄金数量等于经过格子的黄金之和目标是最大化收集的黄金总量。本质是寻找一条不重复访问非零格子的路径使路径上黄金总和最大。2.2 思路讲解本题与单词搜索的思路完全一致都是回溯DFS只是目标从“匹配单词”变成了“求和最大”。我们可以遍历所有非零格子作为起点从起点出发进行深度优先搜索每次向四个方向探索并记录当前路径的黄金总和。回溯恢复现场每进入一个格子将其标记为已访问递归返回后取消标记以便其他路径使用。剪枝只有格子未被访问且黄金非零时才进入。更新最大值每次到达一个无法继续的位置或递归过程中时用当前路径和更新全局最大值。无需考虑起点选择因为所有非零格子都可能作为起点遍历所有即可。三.代码演示class Solution { public: bool check[16][16]; int row,col; int ret 0;//最终的结果 int getMaximumGold(vectorvectorint grid) { row grid.size(),col grid[0].size(); for(int i 0;i row;i) { for(int j 0;j col;j) { //判断这个是不是能走的格子 if(grid[i][j] ! 0) { check[i][j] true; dfs(grid,i,j,grid[i][j]); //恢复 check[i][j] false; } } } return ret; } int dx[4] {0,0,1,-1}; int dy[4] {1,-1,0,0}; void dfs(vectorvectorint grid,int i,int j,int path) { ret max(ret,path); for(int k 0;k 4;k) { int x i dx[k],y j dy[k]; if(x 0 y 0 x row y col !check[x][y] grid[x][y] ! 0) { check[x][y] true; dfs(grid,x,y,path grid[x][y]); check[x][y] false; } } } };四.代码讲解一、全局变量与数据结构check[16][16]布尔数组记录每个格子是否已被当前路径访问过。题目网格最大为 15×15大小 16 足够。row、col成员变量存储网格的行数和列数。ret整型变量记录当前找到的最大黄金收集量初始为 0。方向数组dx[4]、dy[4]表示上下左右四个方向的偏移量方便探索相邻格子。二、主函数getMaximumGold获取网格的行数row和列数col并赋值给成员变量。遍历整个网格如果某个格子上的黄金数量不为 0则以此格子作为起点开始搜索将该格子标记为已访问check[i][j] true。调用递归函数dfs从该格子出发当前路径黄金总和初始为grid[i][j]。递归返回后恢复现场将该格子标记为未访问check[i][j] false以便其他起点或分支能够使用。遍历完所有起点后返回全局最大值ret。三、递归函数dfsdfs(grid, i, j, path)表示当前位于格子(i, j)已收集的黄金总量为path。执行流程如下1. 更新最大值每进入一个格子首先用当前路径和path更新全局最大值ret因为可能在此处停止。注意即使还能继续走也要先记录当前值因为可以在任意位置停止。2. 向四个方向探索使用for循环遍历四个方向计算新坐标(x, y)。对于每个方向检查该格子是否合法边界检查x 0 y 0 x row y col。未访问!check[x][y]。有黄金grid[x][y] ! 0。如果三个条件都满足则将(x, y)标记为已访问check[x][y] true。递归调用dfs(grid, x, y, path grid[x][y])继续收集黄金。递归返回后回溯将(x, y)标记为未访问check[x][y] false以便尝试其他方向或路径。3. 递归终止当四个方向都探索完该层递归自然结束返回上一层。无需额外终止条件因为ret已在进入时更新。四、回溯与恢复现场回溯是本题的核心。当从当前格子出发的某条路径探索完毕时必须将当前格子标记恢复为未访问否则其他路径将无法经过此格子导致漏解。这正是通过check[x][y] false实现的。五、关键细节起点选择遍历所有非零格子作为起点因为黄金矿工可以从任意有黄金的格子出发。方向顺序上下左右四个方向无顺序要求任何顺序均可。路径长度的记录在每次进入格子后立即更新最大值因为可以在任意位置停止无需等到无路可走。剪枝通过check数组和grid[x][y] ! 0条件避免了无效的移动。
