#675
Cut Off Trees for Golf Event
master · 1855 · lc hard +32 · verified · 36.2% accepted · 1,291 likes · top 14%
Description
You are clearing a forest represented as an m x n grid, where:
- 0 means the cell is impassable.
- 1 means the cell is empty and walkable.
- Any value greater than 1 represents a tree with that height, which can also be walked through.
Each step moves you 4-directionally. Trees must be cut in ascending order of height; cutting a tree converts its cell to 1. Starting at (0, 0), return the minimum number of steps to cut every tree, or -1 if it is impossible.
Note: All tree heights are distinct and at least one tree exists.
Example 1:
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:
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.
Example 3:
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.
Code
1
2
3