Robot Across the Warehouse

A warehouse floor is a list of strings of equal length, one per row: '.' is open floor and '#' is a shelf. A robot starts on the top-left square and must reach the bottom-right square. In one move it goes to any of the 8 neighbouring squares: up, down, left, right or diagonally. It can never stand on a shelf or leave the floor.

The robot is too wide to slip between two shelves that touch at a corner, so a diagonal move is allowed only when both squares it cuts past are open. For example, moving from row 0, column 0 down and right to row 1, column 1 needs row 0, column 1 and row 1, column 0 to be open as well.

Write shortest_route(floor) that returns the fewest moves the robot needs, or -1 if it cannot get there (including when the start or the end square is a shelf). A floor of one open square needs 0 moves.

Examples

shortest_route(['...',
                '...',
                '...'])     # returns 2
shortest_route(['..#',
                '#..',
                '...'])     # returns 3
shortest_route(['.#.',
                '#..',
                '...'])     # returns -1

In the second floor, the first diagonal move would cut past the shelf at row 1, column 0, so the robot goes right, down, and then diagonally to the corner. In the third, both squares next to the start are shelves and the diagonal squeezes between them, so the robot is stuck.

Constraints

• 1 to 200 rows and 1 to 200 columns.