Cut Off Trees for Golf Event: BFS on a Matrix Grid

You are given an m x n matrix representing a forest. Each cell contains either 0 (an obstacle you cannot walk through), 1 (empty ground you can walk on), or a number greater than 1 (a tree with that height). You start at position (0, 0) and must cut all trees in order from shortest to tallest. Each step moves one cell up, down, left, or right. Return the minimum total number of steps needed to cut every tree, or -1 if it is impossible.

This is LeetCode 675: Cut Off Trees for Golf Event, a hard problem that combines sorting with repeated BFS on a grid. The trick is recognizing that you do not need one massive search. You break the problem into a sequence of smaller shortest-path problems.

Sort first, then BFS between each pair

The constraint that trees must be cut from shortest to tallest tells you the exact order of destinations. You do not need to decide which tree to visit next. That order is fixed once you sort the tree heights.

After sorting, you have a list of target cells you must visit in sequence. The problem reduces to: for each consecutive pair of targets, find the shortest path on the grid using BFS. Sum all those distances. If any BFS cannot reach the next target (because obstacles block the way), the answer is -1.

Why BFS? Because the grid has uniform edge weights (each step costs 1), BFS gives the shortest path in O(m * n) time per query. You run one BFS for each pair of consecutive trees, and there can be at most m * n trees.

The approach is clean: collect and sort the trees, then run BFS from your current position to the next tree, accumulate the distance, move your position, and repeat.

The solution

from collections import deque

def cut_off_tree(forest):
    m, n = len(forest), len(forest[0])

    trees = []
    for r in range(m):
        for c in range(n):
            if forest[r][c] > 1:
                trees.append((forest[r][c], r, c))
    trees.sort()

    def bfs(sr, sc, tr, tc):
        if sr == tr and sc == tc:
            return 0
        visited = set()
        visited.add((sr, sc))
        queue = deque([(sr, sc, 0)])
        while queue:
            r, c, dist = queue.popleft()
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited and forest[nr][nc] != 0:
                    if nr == tr and nc == tc:
                        return dist + 1
                    visited.add((nr, nc))
                    queue.append((nr, nc, dist + 1))
        return -1

    total = 0
    cur_r, cur_c = 0, 0
    for height, tr, tc in trees:
        steps = bfs(cur_r, cur_c, tr, tc)
        if steps == -1:
            return -1
        total += steps
        cur_r, cur_c = tr, tc

    return total

Walking through an example

Consider the forest grid where row 0 is [1, 2, 3], row 1 is [0, 0, 4], and row 2 is [7, 6, 5]. The trees sorted by height are: 2 at (0,1), 3 at (0,2), 4 at (1,2), 5 at (2,2), 6 at (2,1), and 7 at (2,0).

You start at (0,0). BFS to tree 2 at (0,1) costs 1 step. Then BFS from (0,1) to tree 3 at (0,2) costs 1 step. From (0,2) to tree 4 at (1,2) is 1 step down. From (1,2) to tree 5 at (2,2) is 1 step down. From (2,2) to tree 6 at (2,1) is 1 step left. Finally from (2,1) to tree 7 at (2,0) is 1 step left. The total is 6 steps.

Notice how the obstacles at (1,0) and (1,1) did not block any of these paths because the sorted order happened to follow a route around them. In a different configuration, obstacles could force longer detours or make the answer -1.

Complexity

There are at most m * n trees, so you run BFS up to m * n times. Each BFS visits at most m * n cells. That gives O((m * n)^2) total time, which simplifies to O(m^2 * n^2). The space is O(m * n) for the BFS visited set and the queue. Sorting the trees costs O(k log k) where k is the number of trees, but that is dominated by the BFS work.

Edge cases

• Starting cell is 0: The problem guarantees you start at (0,0) and can walk on it, but if forest[0][0] were 0, you could not move at all. Return -1.
• No trees to cut: If every cell is 0 or 1, there are no trees with height greater than 1. Return 0 since no cutting is needed.
• Unreachable tree: Obstacles completely surround a tree. BFS returns -1, so the overall answer is -1.
• Single cell grid: If the grid is 1x1, either it has a tree (cut it with 0 steps since you are already there) or it does not (return 0).

The building blocks

BFS on a grid

BFS is the standard algorithm for finding the shortest path in an unweighted graph. On a matrix grid, each cell is a node and edges connect to the four adjacent cells. You use a queue, process cells level by level, and the first time you reach the target is guaranteed to be the shortest path. This building block appears in dozens of grid problems.

Sorting to determine order

Many problems hide their structure behind an unsorted list. Here the key insight is that the cutting order is simply the sorted order of tree heights. Once you sort, the problem becomes sequential: visit targets one by one. This "sort to reveal structure" pattern is useful whenever the problem specifies a specific ordering criterion.

Decomposing into subproblems

Instead of one complex search, you break the task into many smaller searches. Each BFS between consecutive trees is independent once you know the start and end positions. This decomposition pattern, solving a big problem as a sequence of smaller identical subproblems, shows up in path planning, scheduling, and many graph problems.

From understanding to recall

You have just walked through the complete solution for cutting trees in sorted height order using repeated BFS. The approach has two key pieces: sort the trees, then run BFS between each consecutive pair. It is easy to follow when explained, but reproducing it under time pressure means remembering both the decomposition insight and the BFS implementation details.

The pattern here, "sort targets then find shortest paths between consecutive ones," is reusable in any problem where you must visit locations in a specific order on a grid. Drilling this with spaced repetition means that the next time you see a grid traversal problem with ordered targets, the decomposition comes to mind instantly instead of requiring rediscovery.

Related posts

• Number of Islands - BFS/DFS on a grid to find connected components, the most fundamental matrix traversal problem
• 01 Matrix - Multi-source BFS on a matrix to find shortest distances, a close cousin of the per-tree BFS used here
• Minimum Path Sum - Grid traversal with cost accumulation, using DP instead of BFS because edge weights vary