你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 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] <= 109
解题思路：排序 + bfs
这道题其实难在题目的理解以及问题的转化！首先这道题并不像例子中画的那么巧那么简单，它可能是这样子的：
此时就不能单纯的从 [0, 0] 开始砍树了，而是要找最低也就是最小数值的位置开始砍。砍的过程是需要按照树的高度从低向高砍，而砍完的那些树就变成了 1，表示地面，但因为有可能高度上临近的树并不遵循从低到高，所以砍树之前可能要先移动到临近高度位置的树那里才开始砍，如下图所示：
因为画图失误，导致上图中出现了两个 10 高度的树，而题目给出的例子是不会存在相同高度的，注意下！
搞清楚砍树规则后，就能明白想一次 bfs 来解决问题是不太可能的，因为控制起来会很复杂！
此时换一种思路来解决问题：对树的高度进行从小到大的排序，顺便存储其坐标，然后调用 bfs 函数去求出每个相邻高度坐标之间的步数也就是距离，最后将这些距离累加起来，就是整个砍树所需要的步数！
比如上图中的例子，按照高度排序（0 不算，它是不能到达的）就是 5、7、9、10、11、13、14、16、17、19、21、26，然后先从高度为 5 的树的坐标开始，调用 bfs 函数求出其到达高度为 7 的树所需要的步数；求完之后再从高度为 7 的树的坐标开始，调用 bfs 函数求出其到达高度为 9 的树所需要的步数，后面以此类推……
相当于我们把一个大问题，也就是砍掉所有的树，分解为一个一个小问题，也就是一棵一棵树的砍，这样子一来 bfs 函数所要完成的任务就是求出两个坐标之间的距离，这对我们来说就是小问题！
只不过要注意几点细节问题：
- 因为我们需要按照树的高度从小到大排序，而又因为起点的树的高度有可能列入了砍树序列中，并且不是排在起点，所以我们在开始砍树的时候，必须显式的从起点也就是
[0, 0]处开始，而不能从排完序的数组的最小高度的树坐标开始，那可能不是起点！ - 在进入
bfs函数时候先要判断一下当前坐标和目标坐标是否相同，相同的话则直接返回0即可，因为砍树序列中可能因为高度问题加入了[0,0]坐标，而bfs函数的参数a和b也有可能是[0,0]，如果不做处理的话，是会多计算一份关于起点的步数的，结果就错了！ - 在
bfs函数中需要使用used数组标记已经走过，来防止死循环。 - 在
bfs函数中并不需要真的将当前要砍的树的高度变成1，因为在这道题中有些路径是要重复走的，而只要forest[i][j]是大于1的，那么就可以走，并且我们已经有了要砍树的序列了，不担心是否要修改的问题，所以综上所述就不需要将其改为1。
剩下的问题就按之前遇到的题那样子处理了，具体参考代码：
class Solution {
private:
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int m, n;
public:
int cutOffTree(vector<vector<int>>& forest) {
m = forest.size(), n = forest[0].size();
// 1. 对砍树的顺序进行排序（注意这里是有可能将[0,0]起点也列入砍树序列并且不是排在起点，所以下面处理时候要注意）
vector<pair<int, int>> tree;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(forest[i][j] > 1)
tree.push_back({i, j});
}
}
sort(tree.begin(), tree.end(), [&](const pair<int, int>& p1, const pair<int, int>& p2){
return forest[p1.first][p1.second] < forest[p2.first][p2.second];
});
// 2. 根据排序后的砍树顺序，累加每次从当前位置到下一个砍树点的步数，直到所有树都砍完，或者如果被堵住则直接返回-1
// 因为上面排序时候有可能把[0,0]也列入了砍树顺序，并且可能拍在其它树的后面，
// 但是我们必须从[0,0]开始砍，所以这里就显示的从[0,0]开始砍
int ret = 0;
int x = 0, y = 0;
for(int i = 0; i < tree.size(); ++i)
{
int step = bfs(forest, x, y, tree[i]);
// 如果走不通则直接返回-1，说明没办法把树砍完
if(step == -1)
return -1;
ret += step;
x = tree[i].first, y = tree[i].second; // 别忘了更新砍树起点
}
return ret;
}
// a和b是当前位置坐标，target是目标位置的坐标
int bfs(vector<vector<int>>& forest, int a, int b, const pair<int, int>& target)
{
// 因为砍树序列中可能加入了[0,0]，而a和b也有可能是[0,0]，所以需要判断一下
if(a == target.first && b == target.second)
return 0;
queue<pair<int, int>> bfs;
bfs.push({a, b});
// 防止死循环，要设置位置已走过
bool used[51][51] = { 0 };
used[a][b] = true;
int step = 0;
while(!bfs.empty())
{
step++;
int size = bfs.size();
while(size--)
{
auto [x, y] = bfs.front();
bfs.pop();
for(int i = 0; i < 4; ++i)
{
int newx = x + dx[i], newy = y + dy[i];
// 如果是终点的话直接返回step
if(newx == target.first && newy == target.second)
return step;
if(newx >= 0 && newy >= 0 && newx < m && newy < n && forest[newx][newy] != 0 && used[newx][newy] != true)
{
bfs.push({newx, newy});
used[newx][newy] = true;
}
}
}
}
return -1;
}
};