미로 탈출

수진은 어두운 미로의 한쪽 끝에 갇혀 버렸고, 그녀의 시야가 흐려져서 미로를 통과하는 길을 찾기가 어렵습니다.

미로은 장애물로 가득한 직사각형 셀(2≤N≤20)이 있는 N×N 그리드로 설명됩니다. 수진는 왼쪽 하단 구석(셀 1,1)에서 시작하여 오른쪽 상단 구석(셀 N,N)으로 이동하려고 합니다. 당신의 역할은 그녀에게 '전진', '왼쪽으로 90도 회전', 또는 '오른쪽으로 90도 회전' 중 하나인 일련의 명령을 통해 그녀를 안내하는 것입니다. 당신은 그녀를 목적지로 안내할 수 있는 가장 짧은 명령을 내려야 합니다. 그리드 밖(즉, 미로 벽 안) 또는 장애물로 수진을 움직이도록 지시하면 그녀는 움직이지 않고 시퀀스에 있는 다음 명령으로 건너뜁니다.

불행히도, 수진은 그녀가 위쪽(셀 1,2 쪽)을 향하고 있는지, 오른쪽(셀 2,1 쪽)을 향하고 있는지 알지 못합니다. 당신은 그녀가 어느 방향을 보고 있는지에 관계없이 그녀를 목표지까지 안내할 수 있는 가장 짧은 길을 찾아야 합니다. 그녀가 목표지에 도달하면 더 이상의 명령을 무시할 것입니다.

입력의 첫 번째 줄에는 N이 포함되어 있습니다.

다음 N줄의 각 줄에는 정확히 N개의 문자가 있는 문자열이 포함되어 있으며, 이것은 헛간을 나타냅니다. 마지막 줄의 첫 번째 문자는 셀 1,1입니다. 첫 번째 줄의 마지막 문자는 셀 N, N입니다.

각 문자는 장애물을 나타내는 H나 빈 칸을 나타내는 E가 될 것입니다.

1,1이 위치한 셀과 N,N이 위치한 셀은 반드시 빈 칸이며, 더욱이 두 셀을 잇는 빈 칸의 경로가 있음이 보장됩니다.

출력의 한 줄에는 수진을 목표지로 안내할 가장 짧은 길의 길이를 출력합니다, 그녀가 시작할 때 위를 보든 오른쪽을 보든 상관없이.