안대 낀 스피드러너

안대를 껴서 화면을 보지 못하는 채로 게임을 빨리 깨는 것을 "blindfolded speedrun"이라고 한다.

어느 어드벤처 게임의 blindfolded speedrun 가이드북을 쓰다가 난관에 부딪혔다. 문제가 되는 구간 자체는 어렵지 않다. 장애물이 격자 형태로 놓여 있고, 왼쪽 아래에서 출발해 오른쪽 위로 가기만 하면 되는 간단한 구간이다. 장애물도 게임을 켤 때마다 무작위로 배치되는 것이 아니라 위치가 고정되어 있다. 문제는 처음에 어느 방향을 보고 서 있는지가 무작위라는 점이다. 안대를 꼈으니 방향을 알 방법이 없다.

$N \times N$ 격자가 있다. 몇몇 칸에는 거대한 장애물이 있어서 지나갈 수 없고, 나머지 칸은 비어 있어서 자유롭게 지나갈 수 있다. 격자 바깥은 벽으로 둘러싸여 있어서 밖으로 나갈 수 없다. 주인공은 처음에 왼쪽 아래 칸에 있다. 어느 방향을 보고 있는지는 모르지만 위쪽과 오른쪽 중 하나인 것은 확실하다. 주인공은 매초 "전진", "좌회전", "우회전" 중 하나만 할 수 있고, 각 행동에는 1초가 걸린다. 전진하려는데 앞에 장애물이나 벽이 있으면 그 자리에 그대로 있는다.

처음 방향이 어느 쪽이든 오른쪽 위 칸에 도착하게 만드는 가장 짧은 행동 배열을 구해야 한다. 도착하면 바로 컷신이 재생되므로 도착한 뒤에 다른 칸으로 벗어나는 일은 없다.

첫째 줄에 $N$이 주어진다. ($2 \le N \le 20$)

다음 $N$개의 줄에는 격자의 각 행을 나타내는 길이 $N$의 문자열이 위쪽 행부터 차례로 주어진다. E는 빈 칸이고, H는 장애물이다.

왼쪽 아래 칸과 오른쪽 위 칸은 항상 E이고, 왼쪽 아래에서 오른쪽 위로 가는 경로가 항상 존재한다. (그렇지 않으면 잘못 만든 게임이다.)

가이드북에 쓸 수 있는 행동 배열의 최소 길이를 출력한다.

예제에서 "전진, 우회전, 전진, 전진, 좌회전, 전진, 좌회전, 전진, 전진"의 순서를 따르면 처음에 위쪽을 보고 있었을 때는 6초, 오른쪽을 보고 있었을 때는 9초 만에 도착한다.