Blindfolded speedrunner

Time limit2sMemory limit512 MB

Summary

Find the shortest fixed action sequence that walks a blindfolded hero from the bottom-left to the top-right cell of an N x N grid regardless of whether the initial facing is up or right.

Level: Medium7 of 10
Topics: BFS, Graph, Simulation, Implementation
Solved: No attempts yet

Problem

Beating a game as fast as possible while wearing a blindfold, without seeing the screen, is called a "blindfolded speedrun".

While writing a blindfolded speedrun guide for an adventure game, you run into a problem. The troublesome part is not hard in itself. Obstacles are placed on a grid, and you only need to go from the bottom-left corner to the top-right corner. The obstacles are not even placed randomly each time the game starts; their positions are fixed. The problem is that the direction the hero initially faces is random. With a blindfold on, you have no way to know it.

There is an $N \times N$ grid. Some cells contain huge obstacles and cannot be entered; the other cells are empty and can be passed freely. The grid is surrounded by walls, so the hero cannot leave it. The hero starts in the bottom-left cell. You do not know which way the hero is facing, but it is certainly either up or right. Every second the hero performs exactly one of "forward", "turn left", and "turn right", and each action takes 1 second. If the hero tries to move forward while an obstacle or a wall is directly ahead, the hero stays in place.

Find the shortest sequence of actions that brings the hero to the top-right cell regardless of the initial direction. A cutscene plays as soon as the hero arrives, so after arriving the hero never leaves that cell.

Input

The first line contains $N$ ( $2 \le N \le 20$ ).

Each of the next $N$ lines contains a string of length $N$ describing one row of the grid, from the top row to the bottom row. E is an empty cell and H is an obstacle.

The bottom-left and top-right cells are always E, and a path from the bottom-left cell to the top-right cell always exists. (Otherwise the game would be broken.)

Output

Print the minimum length of an action sequence that can be written in the guide.

Hint

In the sample, following "forward, turn right, forward, forward, turn left, forward, turn left, forward, forward" brings the hero to the goal in 6 seconds if they started facing up, and in 9 seconds if they started facing right.

Examples1

Example 1
Input
```
3
EHE
EEE
EEE
```
Expected output
```
9
```