算法日常・每日刷题--＜BFS最短路径＞4

675. 为高尔夫比赛砍树 - 力扣LeetCode675. 为高尔夫比赛砍树 - 你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示 在这个矩阵中 * 0 表示障碍无法触碰 * 1 表示地面可以行走 * 比 1 大的数 表示有树的单元格可以行走数值表示树的高度每一步你都可以向上、下、左、右四个方向之一移动一个单位如果你站的地方有一棵树那么你可以决定是否要砍倒它。你需要按照树的高度从低向高砍掉所有的树每砍过一颗树该单元格的值变为 1即变为地面。你将从 (0, 0) 点开始工作返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树返回 -1 。可以保证的是没有两棵树的高度是相同的并且你至少需要砍倒一棵树。 示例 1[https://assets.leetcode.com/uploads/2020/11/26/trees1.jpg]输入forest [[1,2,3],[0,0,4],[7,6,5]]输出6解释沿着上面的路径你可以用 6 步按从最矮到最高的顺序砍掉这些树。示例 2[https://assets.leetcode.com/uploads/2020/11/26/trees2.jpg]输入forest [[1,2,3],[0,0,0],[7,6,5]]输出-1解释由于中间一行被障碍阻塞无法访问最下面一行中的树。示例 3输入forest [[2,3,4],[0,0,5],[8,7,6]]输出6解释可以按与示例 1 相同的路径来砍掉所有的树。(0,0) 位置的树可以直接砍去不用算步数。 提示 * m forest.length * n forest[i].length * 1 m, n 50 * 0 forest[i][j] 109https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/题目核心理解规则必须按照树高度从小到大依次砍树不能乱序每次砍完树该位置变为地面1地图0 障碍不能走1 地面1 树可通行起点(0,0)每上下左右移动一格算一步求全部砍完的最小总步数无法完成返回-1关键点两棵树高度互不相同整体解题思路收集所有树遍历矩阵把所有高度 1 的树记录(高度, x坐标, y坐标)排序树列表按照高度升序确定砍树顺序逐段 BFS 求最短路径初始起点cur_x0, cur_y0依次取出下一棵要砍的树坐标BFS 求【当前位置 → 目标树】的最短步数一旦某一段 BFS 不可达直接返回-1累加步数更新当前坐标为目标树坐标全部遍历完成返回总步数#include vector #include queue #include algorithm using namespace std; class Solution { public: int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; int m, n; // BFS求起点(sx,sy) 到终点(tx,ty) 的最短距离不可达返回 -1 int bfs(vectorvectorint forest, int sx, int sy, int tx, int ty) { if(sx tx sy ty) return 0; vectorvectorbool vis(m, vectorbool(n, false)); queuepairint, int q; q.push({sx, sy}); vis[sx][sy] true; int step 0; while(!q.empty()) { int sz q.size(); step; for(int i 0; i sz; i) { auto [x, y] q.front(); q.pop(); for(int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if(nx 0 nx m ny 0 ny n !vis[nx][ny] forest[nx][ny] ! 0) { if(nx tx ny ty) return step; vis[nx][ny] true; q.push({nx, ny}); } } } } return -1; // 无法到达 } int cutOffTree(vectorvectorint forest) { m forest.size(); n forest[0].size(); vectortupleint, int, int trees; // 1. 收集所有树 (高度,x,y) for(int i 0; i m; i) { for(int j 0; j n; j) { if(forest[i][j] 1) { trees.emplace_back(forest[i][j], i, j); } } } // 2. 按树高度升序排序 sort(trees.begin(), trees.end()); int cur_x 0, cur_y 0; int total_step 0; // 3. 依次砍每一棵树 for(auto t : trees) { int h get0(t); int tx get1(t); int ty get2(t); int dist bfs(forest, cur_x, cur_y, tx, ty); if(dist -1) return -1; total_step dist; cur_x tx; cur_y ty; } return total_step; } };