Clear Obstacles in Height Order, Minimum Walk
A field grid has impassable cells (0), walkable ground (1), and trees of distinct heights (>1). Starting at the top-left, you must cut all trees in strictly increasing height order, walking the fewest total steps.
Problem
Given an m x n grid where 0 = cannot walk, 1 = walkable, and any value > 1 = a tree of that height, you start at (0,0) and must cut all trees in order of increasing height. After cutting a tree its cell becomes 1. Return the minimum total steps to cut all trees, or -1 if impossible. Steps move between adjacent walkable cells.
Input
An m x n integer grid (list of lists).
Output
An integer: total minimum steps, or -1.
Constraints
- 1 <= m, n <= 50
- 0 <= grid[i][j] <= 10^9
- Tree heights are distinct; (0,0) is walkable or a tree.
Examples
Example 1
Input
grid = [[1,2,3],[0,0,4],[7,6,5]]
Output
6
Cut heights 2,3,4,5,6,7 in order; total walk is 6 steps.
Example 2
Input
grid = [[1,2,3],[0,0,0],[7,6,5]]
Output
-1
The lower band is walled off; trees are unreachable in order.