C++ Solution


  • 0
    class Solution {
    public:
        int cutOffTree(vector<vector<int>>& forest) {
            if (forest.empty() || forest[0].empty())
                return -1;
            int rows = forest.size(), columns = forest[0].size(), res = 0;
            vector<vector<int>> trees;
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < columns; ++j) {
                    int height = forest[i][j];
                    if (height > 1)
                        trees.push_back({i, j, height});
                }
            }
            sort(trees.begin(), trees.end(), [](vector<int> &a, vector<int> &b) {
                return a[2] < b[2];
            });
            int sx = 0, sy = 0;
            for (auto &tree : trees) {
                int tx = tree[0], ty = tree[1];
                int dist = findDist(sx, sy, tx, ty, forest);
                if (dist < 0) return -1;
                res += dist;
                sx = tx;
                sy = ty;
            }
            return res;
        }
        
        int findDist(int startX, int startY, int targetX, int targetY, vector<vector<int>>& forest) {
            queue<vector<int>> queue;
            queue.push({startX,startY, 0});
            int rows = forest.size(), columns = forest[0].size();
            vector<vector<bool>> visited(rows, vector<bool>(columns, false));
            visited[startX][startY] = true;
            while (!queue.empty()) {
            int size = queue.size();
                auto first = queue.front();
                queue.pop();
                int x = first[0], y = first[1], step = first[2];
                if (x == targetX && y == targetY)
                    return step;
                for (int i = 0; i < 4; ++i){
                        int nextX = x + dx[i], nextY = y + dy[i];
                        if (nextX< 0 || nextX >= rows || nextY < 0 || nextY >= columns ||
                            forest[nextX][nextY] == 0 || visited[nextX][nextY])
                            continue;
                        queue.push({nextX, nextY, step + 1});
                        visited[nextX][nextY] = true;
                }
            }
            return -1;
        }
    
    private:
        int dx[4] = {1, 0, -1, 0};
        int dy[4] = {0, 1, 0, -1};
        
        
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.