#675

Hard

auto_awesomeArray plus Breadth-First Search

LeetCode Problem Workspace

Cut Off Trees for Golf Event

Determine the minimum steps to cut all trees in a forest matrix in ascending height order using BFS traversal and priority queue.

array breadth first search heap priority queue matrix

Problem Statement

You are given a forest represented as an m x n matrix where each cell can be 0 (obstacle), 1 (empty land), or a positive integer representing a tree height. You need to cut off all trees in increasing order of their height, starting from the shortest tree. You can move one step at a time in four directions: north, south, east, and west, and cannot cross obstacles.

After cutting a tree, its cell becomes empty land (1). Determine the minimum number of steps required to cut all trees in order. If it is impossible to reach any tree, return -1. Constraints: forest dimensions up to 50x50, all tree heights distinct, and you may start at (0,0) if it contains a tree.

Examples

Example 1

Input: forest = [[1,2,3],[0,0,4],[7,6,5]]

Output: 6

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

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

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.length
n == forest[i].length
1 <= m, n <= 50
0 <= forest[i][j] <= 109
Heights of all trees are distinct.

Solution Approach

Sort Trees by Height

Traverse the forest and record positions and heights of all trees. Use a min-heap (priority queue) to ensure trees are cut in increasing order. Sorting guarantees BFS always targets the next shortest tree.

Breadth-First Search Between Trees

For each consecutive tree, perform BFS from the current position to the target tree to find the minimum steps. Track visited cells to avoid revisiting and handle obstacles (0 cells). Return -1 immediately if the tree is unreachable.

Accumulate Steps and Update Forest

After reaching a tree, add the BFS distance to the total steps. Mark the cell as 1 to simulate cutting. Repeat until all trees are cut. This ensures accurate step counting while maintaining BFS traversal efficiency.

Complexity Analysis

Metric	Value
Time	O((RC)^2)
Space	O(R*C)

Time complexity is O((R C)^2) because BFS is performed for each of up to R C trees on an R C grid. Space complexity is O(R C) for BFS queue and visited matrix.

What Interviewers Usually Probe

Candidate uses BFS for shortest path between trees.
Candidate correctly handles blocked paths and returns -1 when unreachable.
Candidate sorts trees and uses priority queue to ensure correct cutting order.

Common Pitfalls or Variants

Common pitfalls

Failing to cut trees strictly by increasing height.
Not checking if a tree is unreachable, leading to wrong total steps.
Inefficient BFS or repeated calculations for the same paths.

Follow-up variants

Forest with multiple trees of same height requiring tie-breaking by position.
Allow diagonal movement between cells for cutting trees.
Large sparse forest where BFS optimization with pruning is necessary.

FAQ

What is the main algorithmic pattern for Cut Off Trees for Golf Event?

The problem primarily uses Array plus Breadth-First Search with a priority queue to manage tree cutting order.

Why use a heap in this problem?

A min-heap ensures trees are cut in increasing height order, which is required for the golf event.

How do I handle unreachable trees?

During BFS, if the target tree cannot be reached due to obstacles, immediately return -1 to indicate impossibility.

Can BFS be optimized for large forests?

Yes, you can prune visited paths and terminate BFS early when reaching the target tree to save computation.

Do I need to update the forest after cutting a tree?

Yes, mark the cell as 1 to simulate the tree being cut, which affects subsequent BFS traversals.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        def f(i, j, x, y):
            return abs(i - x) + abs(j - y)

        def bfs(i, j, x, y):
            q = [(f(i, j, x, y), i, j)]
            dist = {i * n + j: 0}
            while q:
                _, i, j = heappop(q)
                step = dist[i * n + j]
                if (i, j) == (x, y):
                    return step
                for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
                    c, d = i + a, j + b
                    if 0 <= c < m and 0 <= d < n and forest[c][d] > 0:
                        if c * n + d not in dist or dist[c * n + d] > step + 1:
                            dist[c * n + d] = step + 1
                            heappush(q, (dist[c * n + d] + f(c, d, x, y), c, d))
            return -1

        m, n = len(forest), len(forest[0])
        trees = [
            (forest[i][j], i, j) for i in range(m) for j in range(n) if forest[i][j] > 1
        ]
        trees.sort()
        i = j = 0
        ans = 0
        for _, x, y in trees:
            t = bfs(i, j, x, y)
            if t == -1:
                return -1
            ans += t
            i, j = x, y
        return ans

Continue Practicing

#778 swim in rising water #407 trapping rain water ii #1263 minimum moves to move a box to their target location