BFS & PriorityQueue - w/ comments and prints for visualization
ApproachHave priority queue that stores (height,x,y) for each tree in order of min to max.
Use BFS to find the next available smallest height in priority queue.
## Approach
Have priority queue that stores (height,x,y) for each tree in order of min to max.
Use BFS to find the next available smallest height in priority queue.

## Complexity
Let m=len(forest), n=len(forest[0]), N=m*n

Time: O(N^2) - 692ms (45.50%)
- N^2: N for each BFS search between two elements. The priority queue can have N elements. In total, this is N^2.
- NlogN for building the priority queue, but it gets dominated by N^2.
 
Space: O(N) - 14.9MB (56.88%)
For storing elements in the priority queue.

## Code
```Python []
from typing import List 
import heapq
import collections
import numpy as np #for printing
class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        #print("forest at start: \n{}".format(np.array(forest)))
        m = len(forest)
        n = len(forest[0])
        
        # Store all trees in priority queue in (height,x,y) format
        pq = []
        for x in range(m):
            for y in range(n):
                height = forest[x][y]
                if height > 1:
                    heapq.heappush(pq,(height,x,y))
        #print("heap: {}".format(pq))
        
        # Takes in starting position and next tree position, returns min steps to get to that next tree position
        def bfs(x,y,nextX,nextY) -> int:
            queue = collections.deque([(x,y,0)])
            seen = {(x,y)}
            #print("starting at: ({},{})".format(x,y))
            # Keep BFS searching until we find target tree or tried all paths
            while queue:
                x,y,steps = queue.popleft()

                if x == nextX and y == nextY:
                    # Found the next tree, chop it down and return depth
                    forest[x][y] = 1
                    #print("ending at: ({},{}) after {} steps".format(x,y,steps))
                    return steps

                # Append adjacent nodes (if they are a valid position i.e. height >= 1, within bounds of forest, and not already used)
                for dx,dy in [(-1,0),(0,1),(0,-1),(1,0)]:
                    adjX,adjY = x+dx, y+dy
                    if (0 <= adjX < m and 0 <= adjY < n) and (forest[adjX][adjY] >= 1) and ((adjX,adjY) not in seen):
                        # if (nextX,nextY) == (0,0):
                        #     #print("seen for reaching {},{}: {}".format(nextX,nextY,seen))
                        #     print("queue: {}".format(queue))
                        queue.append((adjX,adjY,steps+1))
                        seen.add((adjX,adjY))
                #print("seen: {}".format(seen))

            # No such path exists
            return -1
        
        # Start from 0,0 and have next be the first smallest tree, and use BFS for the others
        x,y = 0,0
        steps = 0
        # While there are still trees to cut
        while pq:
            _,nextX,nextY = heapq.heappop(pq)
            
            # Find the shortest path to the next tree
            shortestPath = bfs(x,y,nextX,nextY)
            if shortestPath == -1:
                #print("forest: \n{}".format(np.array(forest)))
                return -1
            steps += shortestPath
            #print("total steps taken: {}".format(steps))
            x,y = nextX,nextY

        #print("forest at end: \n{}".format(np.array(forest)))
        return steps
```
```cpp []
class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        int m = forest.size();
        int n = forest[0].size();
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;

        // Store all trees in priority queue as (height, x, y)
        for (int x = 0; x < m; ++x) {
            for (int y = 0; y < n; ++y) {
                if (forest[x][y] > 1) {
                    pq.emplace(forest[x][y], x, y);
                }
            }
        }

        // BFS to find shortest path between two points
        auto bfs = [&](int startX, int startY, int targetX, int targetY) -> int {
            deque<tuple<int, int, int>> queue;
            queue.emplace_back(startX, startY, 0);
            set<pair<int, int>> seen;
            seen.insert({startX, startY});

            // cout << "Starting BFS from: (" << startX << ", " << startY << ")\n";

            while (!queue.empty()) {
                auto [x, y, steps] = queue.front();
                queue.pop_front();

                if (x == targetX && y == targetY) {
                    forest[x][y] = 1;
                    // cout << "Ending at: (" << targetX << ", " << targetY << ") after " << steps << " steps\n";
                    return steps;
                }

                vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
                for (auto [dx, dy] : directions) {
                    int adjX = x + dx, adjY = y + dy;
                    if (adjX >= 0 && adjX < m && adjY >= 0 && adjY < n && forest[adjX][adjY] >= 1 && seen.find({adjX, adjY}) == seen.end()) {
                        queue.emplace_back(adjX, adjY, steps + 1);
                        seen.insert({adjX, adjY});
                    }
                }
            }

            // cout << "No path exists to target: (" << targetX << ", " << targetY << ")\n";
            return -1;
        };

        int x = 0, y = 0, totalSteps = 0;

        while (!pq.empty()) {
            auto [height, nextX, nextY] = pq.top();
            pq.pop();

            // cout << "Processing tree at: (" << nextX << ", " << nextY << ") with height: " << height << "\n";

            int shortestPath = bfs(x, y, nextX, nextY);
            if (shortestPath == -1) {
                // cout << "Forest after failure:\n";
                // for (const auto& row : forest) {
                //     for (int val : row) cout << val << " ";
                //     cout << "\n";
                // }
                return -1;
            }

            totalSteps += shortestPath;
            // cout << "Total steps taken: " << totalSteps << "\n";
            x = nextX;
            y = nextY;
        }

        // cout << "Forest at end:\n";
        // for (const auto& row : forest) {
        //     for (int val : row) cout << val << " ";
        //     cout << "\n";
        // }
        return totalSteps;
    }
};
```
```Java []
class Solution {
    public int cutOffTree(List<List<Integer>> forest) {
        int m = forest.size();
        int n = forest.get(0).size();
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        // Store all trees in priority queue as [height, x, y]
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                int height = forest.get(x).get(y);
                if (height > 1) {
                    pq.offer(new int[]{height, x, y});
                }
            }
        }

        // BFS to find shortest path between two points
        int bfs(int startX, int startY, int targetX, int targetY) {
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{startX, startY, 0});
            Set<String> seen = new HashSet<>();
            seen.add(startX + "," + startY);

            // System.out.println("Starting BFS from: (" + startX + ", " + startY + ")");

            while (!queue.isEmpty()) {
                int[] node = queue.poll();
                int x = node[0], y = node[1], steps = node[2];

                if (x == targetX && y == targetY) {
                    forest.get(x).set(y, 1);
                    // System.out.println("Ending at: (" + targetX + ", " + targetY + ") after " + steps + " steps");
                    return steps;
                }

                int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
                for (int[] dir : directions) {
                    int adjX = x + dir[0], adjY = y + dir[1];
                    if (adjX >= 0 && adjX < m && adjY >= 0 && adjY < n && forest.get(adjX).get(adjY) >= 1 && !seen.contains(adjX + "," + adjY)) {
                        queue.offer(new int[]{adjX, adjY, steps + 1});
                        seen.add(adjX + "," + adjY);
                    }
                }
            }

            // System.out.println("No path exists to target: (" + targetX + ", " + targetY + ")");
            return -1;
        }

        int x = 0, y = 0, totalSteps = 0;

        while (!pq.isEmpty()) {
            int[] tree = pq.poll();
            int nextX = tree[1], nextY = tree[2];

            // System.out.println("Processing tree at: (" + nextX + ", " + nextY + ") with height: " + tree[0]);

            int shortestPath = bfs(x, y, nextX, nextY);
            if (shortestPath == -1) {
                // System.out.println("Forest after failure:");
                // for (List<Integer> row : forest) {
                //     System.out.println(row);
                // }
                return -1;
            }

            totalSteps += shortestPath;
            // System.out.println("Total steps taken: " + totalSteps);
            x = nextX;
            y = nextY;
        }

        // System.out.println("Forest at end:");
        // for (List<Integer> row : forest) {
        //     System.out.println(row);
        // }
        return totalSteps;
    }
}
```
['Breadth-First Search', 'Heap (Priority Queue)', 'Python', 'C++', 'Java', 'Python3']