You are asked to cut off all the trees in a forest for a golf event. The forest is represented as an m x n matrix. In this matrix:
0 means the cell cannot be walked through.1 represents an empty cell that can be walked through.1 represents a tree in a cell that can be walked through, and this number is the tree's height.In one step, you can walk in any of the four directions: north, east, south, and west. If you are standing in a cell with a tree, you can choose whether to cut it off.
You must cut off the trees in order from shortest to tallest. When you cut off a tree, the value at its cell becomes 1 (an empty cell).
Starting from the point (0, 0), return the minimum steps you need to walk to cut off all the trees. If you cannot cut off all the trees, return -1.
Note: The input is generated such that no two trees have the same height, and there is at least one tree needs to be cut off.
Example 1:
Input: forest = [[1,2,3],[0,0,4],[7,6,5]] Output: 6 Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.
Example 2:
Input: forest = [[1,2,3],[0,0,0],[7,6,5]] Output: -1 Explanation: The trees in the bottom row cannot be accessed as the middle row is blocked.
Example 3:
Input: forest = [[2,3,4],[0,0,5],[8,7,6]] Output: 6 Explanation: You can follow the same path as Example 1 to cut off all the trees. Note that you can cut off the first tree at (0, 0) before making any steps.
Constraints:
m == forest.lengthn == forest[i].length1 <= m, n <= 500 <= forest[i][j] <= 109Problem Overview: You are given a grid representing a forest. Cells contain obstacles (0), walkable ground (1), or trees with heights greater than 1. Starting at (0,0), you must cut all trees in increasing order of height while minimizing total steps. If any tree is unreachable, return -1.
Approach 1: BFS Shortest Path Between Trees (Time: O(T * m * n), Space: O(m * n))
The key idea is to cut trees strictly in increasing height order. First collect all tree cells and sort them by height (often using a heap or sorted list). Starting from (0,0), run BFS to compute the shortest path to the next tree. After reaching it, repeat BFS from that position to the next tree in sorted order. Each BFS explores the grid level-by-level using a queue and a visited set to avoid revisiting cells.
This works because the grid has uniform movement cost, so Breadth-First Search always finds the shortest path. Tree ordering can be managed with sorting or a Heap (Priority Queue). In the worst case you run BFS for every tree, giving O(T * m * n) time where T is the number of trees. The grid itself is a classic matrix traversal problem.
Approach 2: Bidirectional BFS for Optimal Path Finding (Time: O(T * m * n), Space: O(m * n))
Bidirectional BFS speeds up individual shortest-path searches by exploring from both the start and target tree simultaneously. Instead of expanding one frontier across the entire grid, two frontiers grow toward each other. When they meet, you have the shortest distance. This reduces the explored search space in practice, especially when trees are far apart.
The algorithm still processes trees in sorted height order, but each step uses two queues and two visited sets. The theoretical worst-case complexity remains O(T * m * n), but the constant factor is lower because each BFS explores fewer cells on average. This approach is useful when the forest grid is large and paths between trees are long.
Recommended for interviews: The standard BFS shortest-path approach is what most interviewers expect. It shows you recognize the grid as an unweighted graph and know how to combine sorting with repeated BFS searches. Bidirectional BFS is a strong optimization discussion if the interviewer asks about improving practical performance.
This approach involves using a BFS algorithm to find the shortest path between the starting point and each tree in increasing order of their heights. We first list all trees with their positions and heights, sort them, and for each sorted tree, compute the shortest path using BFS. If any tree is unreachable, we return -1.
This C solution first uses BFS to calculate the shortest path between trees, starting from (0, 0) and moving to trees in increasing order of their height. The binary search is used to sort the trees based on their height first. If any tree is unreachable during a BFS computation, the function returns -1.
The time complexity of this approach is O(T * m * n) where T is the number of trees. This is because we perform BFS from the starting position to each tree. The space complexity is O(m * n) due to the storage of the queue and visited matrix in BFS.
Using Bidirectional BFS can help in optimizing the pathfinding step by searching from both the start and the goal concurrently. The aim is to decrease the search space substantially as the two searches meet in the middle. This method is an extension to the regular BFS approach, potentially optimizing the traversal cost considerably under specific configurations.
A detailed explanation of handling bidirectional BFS in C would involve structuring two queues for the forward and backward search, ensuring efficient state management overlaps and transitions by interfacing node positions from both directions dynamically, essentially shortening the BFS travel path.
The potential benefits of bidirectional search in space complexity can be realized when effectively reducing the number of explored nodes, as time complexity ideally shortens from O(b^d) to roughly O(b^(d/2)), where b is the branching factor and d the solution depth.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) for Shortest Path | The time complexity of this approach is O(T * m * n) where T is the number of trees. This is because we perform BFS from the starting position to each tree. The space complexity is O(m * n) due to the storage of the queue and visited matrix in BFS. |
| Bidirectional BFS for Optimal Path Finding | The potential benefits of bidirectional search in space complexity can be realized when effectively reducing the number of explored nodes, as time complexity ideally shortens from O(b^d) to roughly O(b^(d/2)), where b is the branching factor and d the solution depth. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS Shortest Path Between Trees | O(T * m * n) | O(m * n) | General solution for grid shortest paths where movement cost is uniform |
| Bidirectional BFS | O(T * m * n) | O(m * n) | When start and target are far apart and you want faster practical performance |
花花酱 LeetCode 675. Cut Off Trees for Golf Event - 刷题找工作 EP55 • Hua Hua • 7,500 views views
Watch 9 more video solutions →Practice Cut Off Trees for Golf Event with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor