LeetCode 675: Cut Off Trees for Golf Event

Problem Restatement

We are given a forest represented as a 2D grid.

Each cell has one of these meanings:

We start at position (0, 0).

We must cut all trees in increasing order of height, from shortest to tallest. After a tree is cut, its cell becomes 1.

Return the minimum number of steps needed to cut all trees.

If any required tree cannot be reached, return -1. The problem states that trees must be cut from lowest height to highest height, and after cutting a tree its cell becomes grass.

Input and Output

Example function shape:

def cutOffTree(forest: list[list[int]]) -> int:
    ...

Examples

Consider:

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

The trees must be cut in height order:

2, 3, 4, 5, 6, 7

One shortest route is:

(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1) -> (2,0)

This takes 6 steps.

So the answer is:

6

Now consider:

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

The bottom row is blocked off by obstacles.

The trees 5, 6, and 7 cannot be reached.

So the answer is:

-1

Another example:

forest = [
    [2, 3, 4],
    [0, 0, 5],
    [8, 7, 6],
]

We start at (0, 0), which already contains the shortest tree.

We can cut it immediately without walking.

The answer is:

6

First Thought: Plan One Full Route

At first, this may look like a route-planning problem.

But the order is fixed. We are not free to choose the next tree.

We must visit trees in increasing height order.

So the problem becomes a sequence of shortest path problems:

start -> shortest tree -> next tree -> next tree -> ...

For each pair of consecutive targets, we need the shortest path through walkable cells.

Since every movement costs exactly one step, BFS is the right shortest path algorithm.

Key Insight

The grid is an unweighted graph.

Each walkable cell is a graph node.

Each move up, down, left, or right is an edge with cost 1.

So the shortest distance between two cells can be found using BFS.

The full answer is the sum of BFS distances between consecutive required positions.

If any BFS fails, the whole task is impossible.

Algorithm

1. Collect all trees as tuples:

(height, row, col)

2. Sort the trees by height.
3. Start from (0, 0).
4. For each tree in sorted order:
   • Use BFS to find the shortest distance from the current position to that tree.
   • If the tree is unreachable, return -1.
   • Add the distance to the answer.
   • Move the current position to the tree position.
5. Return the total answer.

BFS Between Two Cells

The BFS function receives:

start_row, start_col, target_row, target_col

It returns the minimum number of steps needed to reach the target.

BFS uses:

From each cell, try four directions:

up, down, left, right

A neighbor is valid if:

1. It is inside the grid.
2. It has not been visited.
3. Its value is not 0.

Correctness

The trees are sorted by height, so the algorithm visits them in exactly the required order.

For each required move, BFS computes the shortest path from the current position to the next tree because the grid is an unweighted graph and BFS explores cells in increasing distance order.

If BFS cannot reach a tree, then no valid walk exists from the current position to that tree. Since trees must be cut in order, the full task is impossible, so returning -1 is correct.

If BFS reaches the tree, the distance it returns is the minimum number of steps needed for that segment. Since the next required starting position is exactly the tree just cut, adding these segment distances gives the minimum total number of steps for the fixed tree order.

Therefore, the algorithm returns the minimum steps needed to cut all trees, or -1 when this cannot be done.

Complexity

Here, t is the number of trees.

In the worst case, t can be rows * cols, so the time can be written as:

O((rows * cols)^2)

Implementation

from collections import deque
from typing import List

class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        rows = len(forest)
        cols = len(forest[0])

        trees = []

        for r in range(rows):
            for c in range(cols):
                if forest[r][c] > 1:
                    trees.append((forest[r][c], r, c))

        trees.sort()

        def bfs(sr: int, sc: int, tr: int, tc: int) -> int:
            if sr == tr and sc == tc:
                return 0

            queue = deque([(sr, sc, 0)])
            visited = {(sr, sc)}

            directions = [
                (1, 0),
                (-1, 0),
                (0, 1),
                (0, -1),
            ]

            while queue:
                r, c, steps = queue.popleft()

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if nr < 0 or nr >= rows:
                        continue

                    if nc < 0 or nc >= cols:
                        continue

                    if forest[nr][nc] == 0:
                        continue

                    if (nr, nc) in visited:
                        continue

                    if nr == tr and nc == tc:
                        return steps + 1

                    visited.add((nr, nc))
                    queue.append((nr, nc, steps + 1))

            return -1

        answer = 0
        current_row = 0
        current_col = 0

        for _, tree_row, tree_col in trees:
            distance = bfs(
                current_row,
                current_col,
                tree_row,
                tree_col,
            )

            if distance == -1:
                return -1

            answer += distance
            current_row = tree_row
            current_col = tree_col

        return answer

Code Explanation

We first collect all trees:

if forest[r][c] > 1:
    trees.append((forest[r][c], r, c))

Each tree stores its height and position.

Then we sort them:

trees.sort()

This gives the required cutting order.

The BFS starts with:

queue = deque([(sr, sc, 0)])
visited = {(sr, sc)}

Each queue entry stores the row, column, and distance from the start.

For each cell, we try four directions:

directions = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1),
]

We ignore invalid cells, obstacles, and already visited cells:

if forest[nr][nc] == 0:
    continue

if (nr, nc) in visited:
    continue

When the target is found, BFS returns the distance:

if nr == tr and nc == tc:
    return steps + 1

The main loop moves from one tree to the next:

for _, tree_row, tree_col in trees:

If any tree is unreachable:

if distance == -1:
    return -1

Otherwise, add the distance and update the current position.

Testing

def run_tests():
    s = Solution()

    assert s.cutOffTree([
        [1, 2, 3],
        [0, 0, 4],
        [7, 6, 5],
    ]) == 6

    assert s.cutOffTree([
        [1, 2, 3],
        [0, 0, 0],
        [7, 6, 5],
    ]) == -1

    assert s.cutOffTree([
        [2, 3, 4],
        [0, 0, 5],
        [8, 7, 6],
    ]) == 6

    assert s.cutOffTree([
        [1, 2],
    ]) == 1

    assert s.cutOffTree([
        [1],
    ]) == 0

    assert s.cutOffTree([
        [1, 0, 2],
    ]) == -1

    print("all tests passed")

run_tests()

Test meaning: