Java : using PriorityQueue and BFS
Intuition\nUse PriorityQueue to store the tree positions heightwise in the increasing order. Use BFS to calculate distance between successive trees.\n\n# Approa
# Intuition\nUse PriorityQueue to store the tree positions heightwise in the increasing order. Use BFS to calculate distance between successive trees.\n\n# Approach\nNotice that last constraint - Heights of all trees are distinct. So all the trees must be visited sequentially in increasing order of their heights. We store the position of the trees in PriorityQueue and use BFS to get minimum distance between two positions.\n\n# Complexity\n- Time complexity:\nIn the worst case, we are cutting m*n trees and for each time, we are fetching location data from PriorityQueue. So time complexity of this operation is (nm)log(nm). We are performing BFS for each tree with time complexity of O(nm). So, overall time complexity is ((nm)^2)log(nm).\n\n- Space complexity:\nO(nm) - for PriorotyQueue.\n\n# Code\n```\nclass Solution {\n    public int cutOffTree(List<List<Integer>> forest) {\n        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(\n            (a,b) ->forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1])\n        );\n        for(int i=0; i<forest.size(); i++){\n            for(int j=0; j<forest.get(0).size(); j++){\n                if(forest.get(i).get(j) > 1){\n                    pq.add(new int[]{i, j});\n                }\n            }\n        }\n        \n        int x = 0;\n        int y = 0;\n        int steps = 0;\n        while(pq.isEmpty() == false){\n            int[] nextPosition = pq.poll();\n            int reqdStep = BFS(forest, x, y, nextPosition[0], nextPosition[1]);\n            if(reqdStep >= 10000){\n                return -1;\n            }\n            steps += reqdStep;\n            x = nextPosition[0];\n            y = nextPosition[1];\n        }\n        \n        return steps;\n    }\n    \n    int BFS(List<List<Integer>> forest, int x, int y, int newX, int newY){\n        LinkedList<int[]> queue = new LinkedList<int[]>();\n        int[][] dp = new int[forest.size()][forest.get(0).size()];\n        for(int[] arr : dp){\n            Arrays.fill(arr, 10000);\n        }\n        queue.addFirst(new int[]{x,y,0});\n        while(queue.isEmpty() == false){\n            int[] currentPosition = queue.removeLast();\n            x = currentPosition[0];\n            y = currentPosition[1];\n            int countOfSteps = currentPosition[2];\n            if(x<0 || x>=forest.size() || y<0 || y>=forest.get(0).size() || forest.get(x).get(y) == 0){\n            continue;\n            }\n            if(dp[x][y] <= countOfSteps){\n                continue;\n            }\n            dp[x][y] = countOfSteps;\n            if(x == newX && y == newY){\n                return dp[x][y];\n            }\n            queue.addFirst(new int[]{x-1, y, dp[x][y]+1});\n            queue.addFirst(new int[]{x+1, y, dp[x][y]+1});\n            queue.addFirst(new int[]{x, y-1, dp[x][y]+1});\n            queue.addFirst(new int[]{x, y+1, dp[x][y]+1});\n        }\n        return 10000;\n    }\n    \n}\n```
['Breadth-First Search', 'Heap (Priority Queue)', 'Java']