675.为高尔夫比赛砍树

链接：675.为高尔夫比赛砍树
难度：Hard
标签：广度优先搜索、数组、矩阵、堆（优先队列）
简介：你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。如果你无法砍完所有的树，返回 -1 。

题解 1 - cpp

编辑时间：2022-05-23
执行用时：760ms
内存消耗：97.5MB
编程语言：cpp
解法介绍：bfs, 每次从当前值寻找下一个目标。

int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
class Solution {
   public:
    typedef pair<int, int> node;
    int rowLen, colLen;
    int cutOffTree(vector<vector<int>>& forest) {
        rowLen = forest.size(), colLen = forest[0].size();
        vector<int> list;
        for (int row = 0; row < rowLen; row++) {
            for (int col = 0; col < colLen; col++) {
                if (forest[row][col] > 1) list.emplace_back(forest[row][col]);
            }
        }
        sort(list.begin(), list.end(),
             [&](int a, int b) -> bool { return a < b; });
        int ans = 0;
        node prev = make_pair(0, 0);
        for (int i = 0; i < list.size(); i++) {
            int step = findNext(forest, prev, list[i]);
            if (step == -1) return -1;
            ans += step;
        }
        return ans;
    }
    int findNext(vector<vector<int>>& forest, node& start, int target) {
        int step = 0, size = 1;
        queue<node> q;
        vector<vector<bool>> used(rowLen, vector(colLen, false));
        used[start.first][start.second] = true;
        q.push(start);
        while (q.size()) {
            node item = q.front();
            q.pop();
            if (forest[item.first][item.second] == target) {
                start.first = item.first;
                start.second = item.second;
                return step;
            }
            for (int i = 0; i < 4; i++) {
                int nrow = item.first + dirs[i][0],
                    ncol = item.second + dirs[i][1];
                if (nrow < 0 || nrow == rowLen || ncol < 0 || ncol == colLen ||
                    forest[nrow][ncol] == 0 || used[nrow][ncol])
                    continue;
                q.push(make_pair(nrow, ncol));
                used[nrow][ncol] = true;
            }
            if (--size == 0) {
                size = q.size();
                step++;
            }
        }
        return -1;
    }
};

题解 1 - cpp​

题解 1 - cpp