C++ || BFS || Easy solution || Heap 👨🏻‍💻
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves cutting down trees in a forest, where the height of trees is repre
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves cutting down trees in a forest, where the height of trees is represented by a 2D grid. You start at the top-left corner and can only walk in 4 directions: up, down, left, and right. The goal is to cut the trees in order of their height, so you need to navigate from one tree to the next and find the minimum steps needed to achieve this. If it\'s not possible to reach a tree, return -1.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sorting Trees by Height: First, collect all the tree positions in a priority queue sorted by height because trees must be cut in increasing order of their height.\n\n2. BFS for Shortest Path: To move from one tree to another, we perform a Breadth-First Search (BFS). BFS ensures that we find the shortest path between the two trees. If a path doesn\'t exist, return -1.\n\n3. Processing Trees: Start at the initial position (0,0). For each tree (in sorted order), run BFS to find the shortest path. After reaching the current tree, update your starting position and repeat until all trees are processed.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n      O(T\xD7m\xD7n+m\xD7nlog(m\xD7n))\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(mxn)\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    // Check if the cell (i, j) is within the bounds of the grid.\n    bool isSafe(int i, int j, int m, int n) {\n        return i >= 0 && i < m && j >= 0 && j < n;\n    }\n\n    // BFS function to find the shortest path from (currI, currJ) to (nextI, nextJ).\n    int BFS(vector<vector<int>>& forest, int currI, int currJ, int nextI, int nextJ) {\n        int m = forest.size();\n        int n = forest[0].size();\n        int step = 0;\n        vector<vector<bool>> visited(m, vector<bool>(n, false));\n\n        // Start BFS from the current position.\n        visited[currI][currJ] = true;\n        vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n        queue<pair<int, int>> q;\n        q.push({currI, currJ});\n\n        // BFS loop\n        while (!q.empty()) {\n            int size = q.size();\n            while (size--) {\n                int i = q.front().first;\n                int j = q.front().second;\n                q.pop();\n\n                // If we\'ve reached the target tree, return the number of steps.\n                if (i == nextI && j == nextJ) return step;\n\n                // Explore all four directions.\n                for (auto& dir : directions) {\n                    int x = i + dir[0];\n                    int y = j + dir[1];\n\n                    // If it\'s a valid and unvisited cell, and it\'s not a blocked cell (forest[x][y] != 0).\n                    if (isSafe(x, y, m, n) && visited[x][y] == false && forest[x][y] != 0) {\n                        visited[x][y] = true;\n                        q.push({x, y});\n                    }\n                }\n            }\n            step++;  // Increment step count after processing all current level nodes.\n        }\n\n        // If the tree is unreachable, return a large value.\n        return INT_MAX;\n    }\n\npublic:\n    int cutOffTree(vector<vector<int>>& forest) {\n        int m = forest.size();\n        int n = forest[0].size();\n\n        // Priority queue to store trees in increasing order of height.\n        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;\n\n        // Insert all trees (value >= 2) into the priority queue with their coordinates.\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                int num = forest[i][j];\n                if (num >= 2) {\n                    pq.push({num, i, j});\n                }\n            }\n        }\n\n        int lastI = 0, lastJ = 0;  // Start position at (0,0)\n        int step = 0;\n\n        // Process each tree in increasing order of height.\n        while (!pq.empty()) {\n            auto vec = pq.top();\n            pq.pop();\n\n            // Perform BFS to find the shortest path from the last position to the next tree.\n            int pathFinder = BFS(forest, lastI, lastJ, vec[1], vec[2]);\n\n            // If a tree is unreachable, return -1.\n            if (pathFinder == INT_MAX) return -1;\n\n            // Add the steps to the total and update the last position.\n            step += pathFinder;\n            lastI = vec[1];\n            lastJ = vec[2];\n        }\n\n        return step;  // Return the total number of steps.\n    }\n};\n```
['Breadth-First Search', 'Heap (Priority Queue)', 'C++']