公司网站开发费怎么入账,杂志制作 wordpress主题,大型门户网站开发公司,烟台做网站目录
力扣675. 为高尔夫比赛砍树
解析代码 力扣675. 为高尔夫比赛砍树
675. 为高尔夫比赛砍树
难度 困难
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示#xff0c; 在这个矩阵中#xff1a;
0 表示障碍#xff0c;无法触碰1 表示地面…目录
力扣675. 为高尔夫比赛砍树
解析代码 力扣675. 为高尔夫比赛砍树
675. 为高尔夫比赛砍树
难度 困难
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示 在这个矩阵中
0 表示障碍无法触碰1 表示地面可以行走比 1 大的数 表示有树的单元格可以行走数值表示树的高度
每一步你都可以向上、下、左、右四个方向之一移动一个单位如果你站的地方有一棵树那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树每砍过一颗树该单元格的值变为 1即变为地面。
你将从 (0, 0) 点开始工作返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树返回 -1 。
可以保证的是没有两棵树的高度是相同的并且你至少需要砍倒一棵树。
示例 1 输入forest [[1,2,3],[0,0,4],[7,6,5]]
输出6
解释沿着上面的路径你可以用 6 步按从最矮到最高的顺序砍掉这些树。
示例 2 输入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.lengthn forest[i].length1 m, n 500 forest[i][j] 10^9
class Solution {
public:int cutOffTree(vectorvectorint forest) {}
}; 解析代码 先找出砍树的顺序然后按照砍树的顺序一个一个地用 bfs 求出最短路即可。求最短路就是力扣1926. 迷宫中离入口最近的出口。
class Solution {int dx[4] {0, 0, -1, 1};int dy[4] {1, -1, 0, 0};int m 0, n 0;bool vis[51][51];public:int cutOffTree(vectorvectorint forest) {m forest.size(), n forest[0].size();mapint, pairint,int hash; // 数组值和下标按数组值排序for(int i 0; i m; i){for(int j 0; j n; j){if(forest[i][j] 1) // 0不可走1是地面hash[forest[i][j]] {i, j};}}int ret 0;pairint,int start make_pair(0, 0);for(auto [e, end] : hash) // 取下标{int step bfs(forest, start, end);if(step -1)return -1;ret step;start end;}return ret;}int bfs(vectorvectorint forest, pairint,int start, pairint,int end){if(start end)return 0;memset(vis, 0, sizeof(vis)); // 清空之前的数据queuepairint, int q;q.push(start);auto [a, b] q.front();vis[a][b] true;int ret 0;while(!q.empty()){ret;int sz q.size();while(sz--){auto [a, b] q.front();q.pop();for(int i 0; i 4; i){int x a dx[i], y b dy[i];if(x 0 x m y 0 y n forest[x][y] !vis[x][y]){if(x end.first y end.second)return ret;q.push({x, y});vis[x][y] true;}}}}return -1;}
};
