原题链接： 675. 为高尔夫比赛砍树
题目大意
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
0 表示障碍，无法触碰
1 表示地面，可以行走
比1大的数 表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
你将从(0, 0)点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回-1。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
示例：
输入:
[ [1,2,3],
[0,0,4],
[7,6,5]]
输出: 6
输入:
[ [1,2,3],
[0,0,0],
[7,6,5]]
输出: -1
输入:
[ [2,3,4],
[0,0,5],
[8,7,6]]
输出: 6
解释: (0,0) 位置的树，你可以直接砍去，不用算步数。
思路
只要是g[i][j]大于等于1即可走，不管是否已经砍过，因此可先对所有树的高度排序，然后依次计算距离，累加距离为答案。若中间存在某两棵树之间无法达到，则答案为-1。
- 开一个数组，从低到高排序树的高度 O(nmlog(nm))
- 遍历该数组，依次计算两棵树之间的最短距离 O(nm * nm)
代码
class Solution {
public:
struct Tree{
int x, y, h;
bool operator< (const Tree& t) const{
return h < t.h;
}
};
vector<vector<int>> g;
int n, m;
int bfs(Tree start, Tree end){
// 没有两棵树的高度是相同，当起始点{0, 0}有树时返回0
if(start.x == end.x && start.y == end.y) return 0;
// 开始求最短路
const int INF = 0x3f3f3f3f;
vector<vector<int>> dist(n, vector(m, INF));
dist[start.x][start.y] = 0;
queue<Tree> q; // 队列用于存位置x,y
q.push({start.x, start.y, start.h}); // q.push(start);
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
while(q.size()){
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i ++ ){
int x = t.x + dx[i], y = t.y + dy[i];
if(x >= 0 && x < n && y >= 0 && y < m && g[x][y]){
if(dist[x][y] > dist[t.x][t.y] + 1){
dist[x][y] = dist[t.x][t.y] + 1;
if(x == end.x && y == end.y) return dist[x][y];
q.push({x, y});
}
}
}
}
return -1;
}
int cutOffTree(vector<vector<int>>& forest) {
g = forest;
n = g.size(), m = g[0].size();
vector<Tree> trs;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ ){
if(g[i][j] > 1){
trs.push_back({i, j, g[i][j]});
}
}
sort(trs.begin(), trs.end());
Tree last = {0, 0};
int res = 0;
for(auto& tr : trs){
int t = bfs(last, tr);
if(t == -1) return -1;
res += t;
last = tr;
}
return res;
}
};
复杂度
时间复杂度：
O
(
n
2
m
2
)
O(n^2m^2)
O(n2m2)
空间复杂度：
O
(
n
m
)
O(nm)
O(nm)
