시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 45 15 15 34.884%

문제

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

한 어드벤쳐 게임의 blindfolded speedrun 가이드북을 작성하던 중 난관에 봉착했다. 문제가 되는 파트의 난이도 자체가 높은 것은 아니다. 장애물이 격자 형태로 놓여 있고, 왼쪽 아래에서 출발해서 오른쪽 위로 가면 되는 간단한 파트다. 심지어 이 장애물도 게임을 킬 때마다 랜덤으로 배치되는 게 아니라 위치가 고정되어 있다. 문제는 처음에 어느 방향으로 서 있는지가 랜덤이라는 것이다. 안대를 꼈으니 방향을 알 방법이 없다.

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

우리는 어느 방향으로 서 있는지에 관계 없이 오른쪽 위로 도착하도록 할 수 있는 가장 짧은 배열을 작성해야 한다. 도착하면 바로 컷신이 재생되므로 도착한 뒤 다른 칸으로 이탈할 일은 없다.

입력

첫 줄에는 N이 주어진다.

그 다음 N줄에는 격자의 행을 나타내는 길이 N의 스트링이 주어진다. E는 빈 칸이고, H는 장애물이다.

왼쪽 아래와 오른쪽 위는 무조건 E고, 왼쪽 아래에서 오른쪽 위로 가는 경로가 무조건 존재한다. (안 그러면 잘못 만든 게임이다.)

출력

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

예제 입력

3
EHE
EEE
EEE

예제 출력

9

힌트

"전진, 우회전, 전진, 전진, 좌회전, 전진, 좌회전, 전진, 전진"의 순서를 따르면 6초 또는 9초만에 도착할 수 있다.