Cut Off Trees for Golf Event
Hard · Trees · Array · Breadth-First Search · Heap (Priority Queue) · Matrix
Problem
A forest is given as an m x n grid forest:
- 0 is an obstacle you cannot walk through,
- 1 is open ground you can walk on,
- a value greater than 1 is a tree you can walk on; the value is its height.
You start at (0, 0) and may move one cell north, south, east or west per step. You must cut down all trees in order from shortest to tallest. Standing on a tree's cell lets you cut it, after which the cell becomes 1. You may walk over a tree without cutting it. No two trees have the same height, and there is at least one tree.
Return the minimum number of steps needed to cut every tree, or -1 if some tree cannot be reached.
Examples
Input: forest = [[2,3,4],[0,0,5],[8,7,6]] Output: 6
You start on the height-2 tree and then walk the ring past 3, 4, 5, 6, 7, 8, one step each.
Input: forest = [[1,2,3],[0,0,0],[6,5,4]] Output: -1
The row of obstacles cuts off the bottom trees.
Input: forest = [[1,4,1],[2,0,3]] Output: 7
Down to 2 (1 step), back up and across to 3 (4 steps), then back to 4 (2 steps): 7.
Constraints
- m == forest.length, n == forest[i].length
- 1 <= m, n <= 50
- 0 <= forest[i][j] <= 10^9
- All tree heights are distinct
- forest[0][0] != 0
- There is at least one tree
Approaches
- Baseline: relax distances until they settle — time O(T · (m · n)^2), space O(m · n)
Follow-up
With fixed legs, each leg could also use A* with the Manhattan distance as its guide, which explores fewer cells on open ground. The use cases return the length of every leg, and count the reachable trees with a single flood fill.
Related problems
Start free on Cariara · Coding problems · System design studio
