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.
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.
from collections import dequeclass 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
