m × n matrix garden:
- 0 is an impassable cell (a pond or a flower bed);
- 1 is an empty cell you can walk on;
- a number greater than 1 is a cell with a bush, also walkable; the number is the bush's height.
In one step the gardener moves to a neighbouring cell up, down, left or right. Standing on a bush cell, he may trim the bush, and the cell becomes 1. The bushes must be trimmed in strictly increasing order of height, starting with the shortest; walking past a bush without trimming it is allowed.
The gardener starts at cell (0, 0). Return the minimum number of steps needed to trim every bush, or -1 if some bush cannot be reached. If there are no bushes, the answer is 0.garden=[[1, 4, 1], [0, 0, 2], [3, 1, 1]] → 11
First the bush of height 2: (0,0) → (0,1) → (0,2) → (1,2), 3 steps. Then bush 3 at (2,0): (1,2) → (2,2) → (2,1) → (2,0), 3 more steps. The last bush, 4, is at (0,1): 3 steps back to (1,2) and 2 more, for a total of 3 + 3 + 5 = 11.
garden=[[5, 1], [0, 0], [2, 3]] → -1
Bushes 2 and 3 are walled off by an impassable row, so they cannot be reached.
garden=[[2, 1, 3]] → 2
Bush 2 stands on the starting cell, so it is trimmed right away without moving. Then 2 steps to bush 3.
garden=[[1, 4, 1], [0, 0, 2], [3, 1, 1]]
11
Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.