【BFS最短路问题】为高尔夫比赛砍树

输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。

输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
输出：-1
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。

输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
输出：6
解释：可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。

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;
    }
};