지하실의 로봇

The Professor는 또다시 집에 있는 로봇을 잃어버렸다. 잠시 생각한 뒤 교수는 로봇을 지하실에 두고 왔다는 것을 깨달았다.

교수의 집에 있는 지하실은 1 × 1 크기의 칸들로 나뉜 n × m 직사각형으로 표현된다. 일부 칸은 통과할 수 없는 벽이고, 나머지 칸은 통과할 수 있다. 어떤 통과 가능한 칸에서도 변을 맞댄 통과 가능한 칸들을 거쳐 다른 모든 통과 가능한 칸으로 이동할 수 있다. 통과 가능한 칸 하나는 지하실의 출구이다. 로봇은 정확히 하나의 통과 가능한 칸에 놓여 있다. 로봇이 출구 칸에 놓여 있을 수도 있다.

교수는 밤에 로봇을 찾으러 어두운 지하실에 가는 것이 두렵다. 하지만 그에게는 지하실의 도면과 로봇의 리모컨이 있다. 교수는 리모컨을 사용해 로봇에 왼쪽, 오른쪽, 위쪽 또는 아래쪽으로 한 칸 이동하라는 신호를 보낼 수 있다. 로봇이 신호를 받으면 해당 방향으로 이웃한 칸을 통과할 수 있는 경우 요구된 방향으로 이동한다. 그렇지 않으면 로봇은 제자리에 머문다.

교수는 종이에 k개의 명령으로 이루어진 수열을 적었다. 그는 로봇의 초기 위치가 어디이든 이 수열로 로봇을 지하실 밖으로 내보낼 수 있다고 생각한다. 교수는 다른 로봇이 종이에 적힌 내용에 따라 리모컨의 필요한 버튼들을 누르도록 프로그래밍했다. 교수는 프로그램을 실행하고 잠자리에 들려던 바로 그때 한 가지를 깨달았다.

각 명령을 실행하는 데는 에너지가 들며, 교수는 월말에 막대한 전기 요금을 내고 싶지 않다. 따라서 그는 자신이 적은 수열에서, 그 접두사의 실행이 끝난 뒤 로봇을 출구로 이동시킨다는 것을 보장하는 가능한 한 가장 짧은 접두사를 찾고자 한다. 이것이 이 늦은 시간에 교수가 여러분에게 내는 문제이다.

첫째 줄에 세 정수 n, m, k (3 ≤ n, m ≤ 150, 1 ≤ k ≤ 105)가 주어진다. 다음 n개의 줄에는 각각 m개의 문자가 주어지며, 이는 교수의 지하실을 나타낸다. "#"은 벽, "."은 통과 가능한 칸을 나타내고, "E"는 지하실의 출구를 나타낸다(이 칸도 통과할 수 있다). 모든 통과 가능한 칸에서 출구로 이동할 수 있으며, n × m 직사각형의 둘레에 있는 모든 칸은 벽이다. 정확히 하나의 칸이 지하실의 출구이다. 마지막 줄에는 교수가 종이에 적은 명령 수열을 나타내는 k개의 문자가 주어진다. "L", "R", "U", "D"는 각각 왼쪽, 오른쪽, 위쪽, 아래쪽 명령을 나타낸다.

로봇을 출구 칸으로 이동시키는 가능한 접두사 중 가장 짧은 것의 길이를 출력 파일에 출력한다. 다시 말해, 로봇의 초기 위치가 어디였든 접두사의 모든 명령이 실행된 뒤에는 로봇이 출구 칸에 있어야 한다(명령을 실행하는 동안 로봇이 출구 칸에 도달했다가 떠날 수 있지만, 여기서 중요한 것은 로봇의 마지막 위치뿐이다). If Professor가 틀렸으며 어떤 접두사도(전체 수열을 포함해) 로봇을 출구로 이동시킬 수 없다면 "-1"을 따옴표 없이 출력한다. 통과 가능한 칸이 하나뿐이고 그 칸이 출구라면 "0"을 따옴표 없이 출력한다.