Skridskor

Interview

Time limit1sMemory limit1024 MB

Summary

Find the fewest turns for a skater who glides straight until hitting an obstacle, then turns left or right, to exit the east edge of a grid.

Level: Medium5 of 10
Topics: BFS, Shortest path, Simulation
Solved: No attempts yet

Problem

Natalie has bought new skates and decides to try them out at her local ice rink. The rink is a rectangle, and a number of obstacles are placed on the ice. Natalie is on the west side of the rink and wants to reach the east side.

Natalie is not good at skating. When she enters the ice through the entrance, she cannot turn until she hits an obstacle. When she hits the first obstacle, she can choose to turn left or right, then continue straight ahead, and so on. She always turns 90 degrees left or right after hitting an obstacle, and she can only turn when she has hit an obstacle.

Natalie wants to make the trip as simple as possible. What is the minimum number of turns she needs to make to leave the ice on the right side (east)? Natalie always enters the ice at the top left cell and initially skates east (to the right).

The first line contains the integers $R$ and $C$ , separated by a space.

The next $R$ lines each contain $C$ characters, describing the cells of the rink. A '.' means the cell is empty, and '#' means the cell has an obstacle.

Once Natalie leaves the rink on the right side, she is done. If she leaves on any other side (top, bottom, or left), she fails. Natalie always starts at cell $(0,0)$ and skates to the right.

Output

Print one number on a line: the minimum number of turns Natalie needs to make to leave the ice on the right side. It is guaranteed that a solution exists.

Constraints

$3 \le R,C \le 100$

Hint

In the third sample, Natalie first skates east until the first obstacle. She turns right and skates down. She turns right again and skates west, then turns right twice more before reaching the east edge of the ice. In total she makes four turns, so the answer is four.

Examples3

Example 1

Input

6 10
.........#
########.#
#........#
#.########
#.........
##########

Expected output

Example 2
Input
```
3 3
...
...
...
```
Expected output
```
0
```
Example 3
Input
```
5 5
....#
#.#..
#....
.#..#
##.##
```
Expected output
```
4
```