레이팅 미적용베시가 또다시 농부 존의 헛간 반대편에 갇혀 버렸다. 베시는 시력이 몹시 나빠서 헛간을 가로질러 가려면 당신의 도움이 필요하다.
헛간은 \(N \times N\) 격자 모양의 정사각형 칸들로 이루어져 있으며 (\(2 \leq N \leq 20\)), 일부 칸은 비어 있고 일부 칸에는 지나갈 수 없는 건초 더미가 있다. 베시는 왼쪽 아래 모서리(칸 1,1)에서 출발하여 오른쪽 위 모서리(칸 \(N,N\))로 이동하려 한다. 당신은 베시에게 명령의 나열을 알려 주어 길을 안내할 수 있는데, 각 명령은 "앞으로 이동", "왼쪽으로 90도 회전", "오른쪽으로 90도 회전" 중 하나이다. 베시를 목적지까지 안내하는 가장 짧은 명령의 나열을 내리고자 한다. 만약 베시에게 격자 밖(즉, 헛간 벽)이나 건초 더미로 이동하라고 지시하면, 베시는 움직이지 않고 나열의 다음 명령으로 넘어간다.
안타깝게도 베시는 자신이 처음에 위쪽(칸 1,2 방향)을 보고 있는지 오른쪽(칸 2,1 방향)을 보고 있는지 알지 못한다. 어느 경우이든 상관없이 베시를 목표 지점까지 안내할 수 있는 가장 짧은 명령의 나열을 찾아야 한다. 베시는 목표 지점에 도착하면 이후의 명령을 무시한다.
문제 출처: Brian Dean
문제 출처: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에는 헛간을 나타내는, 정확히 \(N\)개의 문자로 이루어진 문자열이 하나씩 주어진다. 마지막 줄의 첫 번째 문자가 칸 1,1이다. 첫째 줄의 마지막 문자가 칸 \(N, N\)이다.
각 문자는 건초 더미를 나타내는 H이거나 빈 칸을 나타내는 E이다.
칸 1,1과 \(N,N\)은 비어 있음이 보장되며, 나아가 칸 1,1에서 칸 \(N, N\)까지 빈 칸으로 이루어진 경로가 존재함이 보장된다.
베시가 위쪽을 보고 시작하든 오른쪽을 보고 시작하든 상관없이 목표 지점까지 안내할 수 있는 가장 짧은 명령 나열의 길이를 한 줄에 출력한다.
cownav.in · 출력을 쓸 파일 cownav.out3
EHE
EEE
EEE9In this example, the instructions "Forward, Right, Forward, Forward, Left,
Forward, Left, Forward, Forward" will guide Bessie to the destination
irrespective of her starting orientation.