Rover Across the Rubble Field

A survey rover crosses a field drawn as grid, a list of equal-length strings: 'S' is the rover's start (exactly one), 'G' is the goal (exactly one), '.' is open ground and '#' is rubble the rover cannot enter.

In one move the rover goes to one of the eight surrounding cells:

• a straight move (up, down, left or right) costs 10 units of battery;
• a diagonal move costs 14 units, and is allowed only when both straight cells beside it are open too (the rover is too wide to squeeze between two blocks of rubble or clip a corner).

Return the smallest amount of battery needed to reach G, or -1 if it cannot be reached.

The setup provides rubble_field(rows, cols, seed, rubble=30), which builds a random field with S in the top-left and G in the bottom-right corner; the larger tests use it. Try it with Run: print(rubble_field(8, 12, 1)).

Examples

Input:  grid = ["S..",
                "...",
                "..G"]
Output: 28
Explanation: two diagonal moves, 14 + 14.

Input:  grid = ["S#",
                "#G"]
Output: -1
Explanation: the only diagonal would clip two blocks of rubble.

Input:  grid = ["S.#",
                ".#.",
                "..G"]
Output: 40
Explanation: the rubble in the centre rules out every diagonal, so the rover goes
down, down, right, right.

Constraints

• 1 <= len(grid), len(grid[0]) <= 120
• exactly one S and one G, on different cells
• the answer never depends on the clock or on randomness

Goals

• Search a grid with eight moves of two different costs
• Estimate the remaining cost with a distance that never overestimates