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


  • 2

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

  • 0

    Straight forward solution.


  • 0
    L

    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.


  • 0

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


  • 0
    S

    What will be the runtime for this solution?


  • 0

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


  • 0
    Z

    @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!!


Log in to reply
 

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