All problems

One Leap Trail

Medium · graph traversal

A hiking map is a rectangular grid of characters: "." is open trail and "#" is a boulder. The hiker starts at the top-left cell and wants to reach the bottom-right cell. Both of those cells are open trail.

A step moves the hiker to a neighbouring cell (up, down, left or right) that is open trail. Boulders cannot be walked onto.

Once during the whole walk, the hiker may also make one leap: if the cell directly next to the hiker, in one of the four directions, is a boulder, and the cell right behind it in the same direction is inside the map and open trail, the hiker can jump over the boulder and land there. A leap counts as one step. Leaping is optional and only one leap is allowed.

Return the smallest number of steps needed to reach the bottom-right cell, or -1 if it cannot be reached.

Examples

Example 1

Input: grid = [[".", "#", "."]]

Output: 1

One leap over the boulder lands on the goal.

Example 2

Input: grid = [[".", ".", "#"], ["#", "#", "#"], [".", ".", "."]]

Output: 3

Leap down over the boulder in the first column, then walk two cells right.

Example 3

Input: grid = [[".", "#", "#", "."]]

Output: -1

A leap clears only one boulder, so the two boulders in a row block the way.

Constraints

• 1 <= rows, cols <= 25
• Every cell is either "." (open trail) or "#" (boulder).
• The top-left and bottom-right cells are open trail.
• All rows have the same length.