이구아나의 명령
면접 대비시간 제한1초메모리 제한512 MB
막힌 칸이 있는 n×n 격자에서 왼쪽 위에서 오른쪽 아래까지 방향과 거리로 이루어진 직선 이동의 최소 개수를 구한다.
문제
이구아나 이기는 옥수수 미로에 갇혔다. 옥수수 미로는 정사각형 격자로 나타낼 수 있으며, 일부 칸은 지나갈 수 없는 옥수수로 막혀 있고 나머지 칸은 비어 있다. 이기는 비어 있는 칸으로만 이동할 수 있다. 이기는 동서남북 네 방향으로 인접한 칸으로 이동할 수 있다.
이기는 미로를 잘 못 찾아서 여러분의 도움이 필요하다. 이기는 미로의 끝에 도달하는 방법을 알려 주는 명령 목록을 적어 달라고 부탁했다. 각 명령은 <방향> <칸 수> 형태이며, <방향>은 North, South, East, West 중 하나이고 <칸 수>는 그 방향으로 이동해야 하는 칸의 수이다. 이기는 기억력이 나빠서, 더 멀리 걸어야 하더라도 명령 목록이 가능한 한 짧기를 원한다.
이기는 미로의 왼쪽 위 칸에서 시작해서 오른쪽 아래 칸에 도달해야 한다. 이기가 끝까지 갈 수 있는 경로가 항상 존재한다고 보장된다.
이기가 미로의 끝에 도달할 수 있도록 주어야 하는 명령의 최소 개수는 몇 개인가?
입력
첫째 줄에는 미로를 나타내는 정사각형 격자의 한 변의 길이 n (2 ≤ n ≤ 100)이 주어진다.
다음에는 n × n 크기의 문자가 주어진다. 칸이 비어 있으면 해당 문자는 마침표(.)이다. 칸이 옥수수로 막혀 있으면 해당 문자는 샵(#)이다.
출력
이기가 미로의 끝에 도달할 수 있도록 주어야 하는 명령의 최소 개수를 출력한다.