> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Cut Off Trees for Golf Event Python Solution

> Tested Python solution for LeetCode 675 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 675, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Breadth-First Search](/catalog/topics/breadth-first-search), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), [Matrix](/catalog/topics/matrix). [View on LeetCode](https://leetcode.com/problems/cut-off-trees-for-golf-event/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 675   # by problem number
lcpy gen -s cut_off_trees_for_golf_event   # by problem name
```

## Problem

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.
* A number greater than `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.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/11/26/trees1.jpg)

```
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](https://assets.leetcode.com/uploads/2020/11/26/trees2.jpg)

```
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.

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/cut_off_trees_for_golf_event/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/cut_off_trees_for_golf_event/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O((mn)^2) each BFS scan is O(mn) and runs once per tree
    # Space: O(mn) for the BFS queue and visited set
    def cut_off_tree(self, forest: list[list[int]]) -> int:
        rows, cols = len(forest), len(forest[0])
        trees = sorted(
            (forest[r][c], r, c) for r in range(rows) for c in range(cols) if forest[r][c] > 1
        )

        def bfs(sr: int, sc: int, tr: int, tc: int) -> int:
            if (sr, sc) == (tr, tc):
                return 0
            seen: set[tuple[int, int]] = {(sr, sc)}
            queue: deque[tuple[int, int, int]] = deque([(sr, sc, 0)])
            while queue:
                r, c, steps = queue.popleft()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if (
                        0 <= nr < rows
                        and 0 <= nc < cols
                        and forest[nr][nc] > 0
                        and (nr, nc) not in seen
                    ):
                        if (nr, nc) == (tr, tc):
                            return steps + 1
                        seen.add((nr, nc))
                        queue.append((nr, nc, steps + 1))
            return -1

        total = 0
        cur_r, cur_c = 0, 0
        for _, tree_r, tree_c in trees:
            dist = bfs(cur_r, cur_c, tree_r, tree_c)
            if dist < 0:
                return -1
            total += dist
            cur_r, cur_c = tree_r, tree_c
        return total
```

## Complexity

| Time | Space |
| - | - |
| O((mn)^2) each BFS scan is O(mn) and runs once per tree | O(mn) for the BFS queue and visited set |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.