LeetCode每日一题（2022/5/23）675. 为高尔夫比赛砍树（困难）

675. 为高尔夫比赛砍树https://leetcode.cn/problems/cut-off-trees-for-golf-event/

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：

0 表示障碍，无法触碰
1 表示地面，可以行走
比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。

你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/cut-off-trees-for-golf-event
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

简单bfs可解

#include <algorithm>
#include <queue>
#include <cstring>using namespace std;
typedef long long int lld;const int N = 60;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };struct p
{int x, y;int h;
};
bool operator<(const p& a, const p& b)
{return a.h < b.h;
}int m, n;
vector<vector<int>> forest;
p trees[N * N];
int visited[N][N];bool check(p tp)
{if (tp.x >= 0 && tp.x < m && tp.y >= 0 && tp.y < n && !visited[tp.x][tp.y] && forest[tp.x][tp.y])return true;return false;
}int bfs(int mx, int my, int nx, int ny)
{if (mx == nx && my == ny)return 0;int ret = 0;queue<p> q;memset(visited, 0, sizeof(visited));q.push(p{ mx, my, 0 });visited[mx][my] = 1;while (!q.empty()){p now = q.front();q.pop();if (now.x == nx && now.y == ny)return now.h;for (int i = 0; i < 4; i++){p tp;tp.x = now.x + dx[i];tp.y = now.y + dy[i];tp.h = now.h + 1;if (check(tp)){q.push(tp);visited[tp.x][tp.y] = 1;}}}return -1;
}class Solution {
public:int cutOffTree(vector<vector<int>>& t_forest) {forest = t_forest;m = forest.size();n = forest[0].size();int cnt = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (forest[i][j] > 1)trees[cnt++] = p{ i, j, forest[i][j] };sort(trees, trees + cnt);int x = 0;int y = 0;int ans = 0;for (int i = 0; i < cnt; i++){int ret = bfs(x, y, trees[i].x, trees[i].y);if (ret == -1)return -1;ans += ret;x = trees[i].x;y = trees[i].y;}return ans;}
};