402369: GYM100739 C Broken robot

Most probably, when you need to move some things from one room to another you just carry those things by hand. However, this is not the case. For such things Informikas uses robots!

The usual task is to take a box from one corner of the room and move it to the opposite one. The room is divided into squares so the robot could easily navigate around (robots, which can navigate in the rooms not divided into squares, are very expensive!). However, in some of those squares there are unmovable obstacles. The robot can not move into those squares, the best he can do is go around.

When the robot was new, he could move stuff around the room in the matter of seconds. However, currently it's a bit broken. It takes one minute to move from one square to the adjacent one. To turn 90 degrees it also takes one minute. And even better, robot can't turn right anymore – only left. Also, robot can only move forward, not sideways – if it is looking at the bottom , but need to move to the square to the right, he first need to turn 90 degrees left (it takes one minute) and then move forward to the target square (one more minute).

You will be given the map of the room. The width and height of the room are always the same and described by the number N. At the beginning the robot is always in the top left square of the room looking south. The target square is one at the bottom right square of the room. When finished, robot should be standing on the bottom right square and also looking south. Your task is to find how long would it take for robot to move from starting position to the target one.

On the first line of the input there is integer N (1 ≤ N ≤ 200) – the size of the field. In the following N lines there are N characters for the each of the squares of the room: '.' for unoccupied square and '#' for occupied one. It is guaranteed that the top left and bottom right squares are unoccupied and that there always is a path between two of those squares.

Output a single integer – the minimal number of minutes it would take the robot to move from the top left to the bottom right square of the room.

1
.

0

2
..
#.

6

2
.#
..

6

In the first test case robot is already standing in the bottom right square and looking south.

In the second test case robot will turn left once, move to other square, turn left three times and then move forward. This will take 1 + 1 + 3 + 1 = 6 minutes.

In the third test case robot will go forward, turn left, go forward and then turn left three times. 1 + 1 + 1 + 3 = 6 minutes in total.