# [Java/C++] Straightforward solution - sorted array + BFS

• My idea to solve this problem is by two steps:

1. Save each `{tree height, tree position}` into an array `heights`, and then sort this array based on its `tree height`. (You can also do this by using `TreeMap` or `PriorityQueue`);
2. Accumulate the shortest steps between each two adajacent points in `heights[]`.

Java version:

``````class Solution {
int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public int cutOffTree(List<List<Integer>> forest) {
if (forest == null || forest.size() == 0) return -1;
int m = forest.size(), n = forest.get(0).size(), res = 0;
//first step: sort the tree position based on its height
List<int[]> heights = new ArrayList<>();
for(int i = 0; i<m; i++){
for(int j = 0; j<n; j++){
if(forest.get(i).get(j) > 1)heights.add( new int[]{forest.get(i).get(j), i, j} );
}
}
Collections.sort(heights, new Comparator<int[]>() {
public int compare(int[] arr1, int[] arr2) {
return Integer.compare(arr1[0], arr2[0]);
}
});
//second step: accumulate the shortest steps between each two adajacent points in heights[].
int start_x = 0, start_y = 0;
for(int i = 0; i<heights.size(); i++){
int cnt_steps = BFS(forest, m, n, start_x, start_y, heights.get(i)[1], heights.get(i)[2]);
if(cnt_steps == -1)return -1;
res += cnt_steps;
start_x = heights.get(i)[1];
start_y = heights.get(i)[2];
}
return res;
}

public int BFS(List<List<Integer>> forest, int m, int n, int start_x, int start_y, int des_x, int des_y){
if(start_x == des_x && start_y == des_y)return 0;
int steps = 0;
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{start_x, start_y});
int[][] visited = new int[m][n];
visited[start_x][start_y] = 1;
while(!q.isEmpty()){
int qsize = q.size();
steps++;
while(qsize-- >0 ){
int[] cur = q.poll();
int cur_x = cur[0], cur_y = cur[1];
for(int k = 0; k<4; k++){
int x = cur_x + dir[k][0], y = cur_y + dir[k][1];
if(x>=0 && x<m && y>=0 && y<n && forest.get(x).get(y) > 0 && visited[x][y] == 0){
if(x == des_x && y == des_y)return steps;
visited[x][y] = 1;
q.add(new int[]{x,y});
}
}
}
}
return -1;
}
}
``````

C++ version:

``````class Solution {
public:
vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int cutOffTree(vector<vector<int>>& forest) {
int m = forest.size(), n , res = 0;
if(m == 0)return -1;
n = forest[0].size();
//first step: sort the tree position based on its height
vector<vector<int>> heights;
for(int i = 0; i<m; i++){
for(int j = 0; j<n; j++){
if(forest[i][j] > 1)heights.push_back({forest[i][j], i, j});
}
}
sort(heights.begin(), heights.end());
//second step: accumulate the shortest steps between each two adajacent points in heights[].
int start_x = 0, start_y = 0;
for(int i = 0; i<heights.size(); i++){
int cnt_steps = BFS(forest, m, n, start_x, start_y, heights[i][1], heights[i][2]);
if(cnt_steps == -1)return -1;
res += cnt_steps;
start_x = heights[i][1], start_y = heights[i][2];
}
return res;
}

int BFS(vector<vector<int>>& forest, int m, int n, int start_x, int start_y, int des_x, int des_y){
if(start_x == des_x && start_y == des_y)return 0;
int steps = 0;
queue<pair<int, int>> q;
q.push({start_x, start_y});
vector<vector<int>> visited(m, vector<int>(n, 0));
visited[start_x][start_y] = 1;
while(!q.empty()){
int qsize = q.size();
steps++;
while(qsize-- >0 ){
int cur_x = q.front().first, cur_y = q.front().second;
q.pop();
for(int k = 0; k<4; k++){
int x = cur_x + dir[k][0], y = cur_y + dir[k][1];
if(x>=0 && x<m && y>=0 && y<n && forest[x][y] > 0 && visited[x][y] == 0){
if(x == des_x && y == des_y)return steps;
visited[x][y] = 1;
q.push({x,y});
}
}
}
}
return -1;
}
};
``````

• Straight forward solution.

• Collections.sort(heights, new Comparator<int[]>() {
public int compare(int[] arr1, int[] arr2) {
return arr1[0] - arr2[0];
}
});

We might want to change "return arr1[0] - arr2[0]" to "Integer.compare(arr1[0], arr2[0])". Try the test case where arr1[0] = Integer.MAX_VALUE and arr2[0] = Interger.MIN_VALUE, you will see what I meant.

• @larrywang2014 Yes, you are right! It might get overflow error. I have modified this part. Thanks!

• What will be the runtime for this solution?

• @SanD I think it's `O(m^2n^2)` in the worst case.

• @Vincent-Cai I have a question about the BFS part, more specifically, why there is the while loop of

``````while (qsize-- > 0) {
...
}
``````

Isn't typical BFS just include one while loop? What is the function of the above while loop? Thanks a lot!!

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