题目描述

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个非负的二维数组表示，在这个数组中：

• 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) 位置的树，你可以直接砍去，不用算步数。

算法

(BFS) $O(n^2m^2)$

1. 首先将所有的树和坐标放到一个数组中，并且按照高度从小到大排序。
2. 接着遍历每一棵树，并通过BFS计算出从上一棵树走到这一棵树需要的最少步数；若无法达到，则答案就是 -1。

时间复杂度

• 排序所有树的时间复杂度为 $O(nm \log (nm))$，遍历每一棵树并BFS的时间复杂度为 $O(n^2 m^2)$，故总时间复杂度为 $O(n^2 m^2)$。

C++ 代码

class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    int bfs(const pair<int, int> &S, const pair<int, int> &T,
            int n, int m, const vector<vector<int>>& forest) {

        vector<vector<int>> dis(n, vector<int>(m, -1));
        queue<pair<int, int>> q;
        dis[S.first][S.second] = 0;
        q.push(S);

        while (!q.empty()) {
            pair<int, int> sta = q.front();
            q.pop();
            if (sta.first == T.first && sta.second == T.second)
                return dis[T.first][T.second];
            for (int i = 0; i < 4; i++) {
                int tx = sta.first + dx[i], ty = sta.second + dy[i];
                if (tx < 0 || tx >= n || ty < 0 || ty >= m || forest[tx][ty] == 0)
                    continue;
                if (dis[tx][ty] == -1) {
                    dis[tx][ty] = dis[sta.first][sta.second] + 1;
                    q.push(make_pair(tx, ty));
                }
            }
        }

        return -1;
    }

    int cutOffTree(vector<vector<int>>& forest) {
        int n = forest.size(), m = forest[0].size();
        vector<pair<int, pair<int, int>>> trees;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (forest[i][j] > 1)
                    trees.push_back(make_pair(forest[i][j], make_pair(i, j)));

        trees.push_back(make_pair(0, make_pair(0, 0)));

        sort(trees.begin(), trees.end());

        int t = trees.size(), ans = 0;

        for (int i = 1; i < t; i++) {
            int d = bfs(trees[i - 1].second, trees[i].second, n, m, forest);
            if (d == -1)
                return -1;
            ans += d;
        }
        return ans;
    }
};