# C++ Solution

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

};
``````

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