카렐 로봇

"robot"이라는 단어는 거의 100년이 되었다. 이 단어는 1920년 체코 작가 카렐 차펙(Karel Čapek)의 SF 희곡 R.U.R.에서 처음 쓰였다. 그를 기려 여러 해 뒤 스탠퍼드 대학교가 교육용 프로그래밍 언어에 Karel이라는 이름을 붙였다. 이 문제에서는 이 언어를 단순화한 버전의 인터프리터를 구현한다.

Karel 언어는 단위 정사각형으로 이루어진 격자에 사는 로봇 Karel을 제어한다. 일부 칸은 비어 있고, 나머지 칸에는 장애물이 있다. Karel은 항상 빈 칸 위에 있고, 동서남북 중 한 방향을 바라본다. 기본 명령은 "앞으로 이동"과 "왼쪽으로 회전" 두 가지다. 언어에는 단순한 조건문과 반복문도 있다. 이 언어의 교육적 가치는 새 프로시저를 정의해 더 복잡한 작업을 처리할 수 있다는 데 있다.

단순화한 언어의 문법은 다음과 같다.

<program>   :=  "" | <command> <program>
<command>   :=  "m" | "l" | <proc-call> |
                "i" <condition> "(" <program> ")(" <program> ")" |
                "u" <condition> "(" <program> ")"
<condition> :=  "b" | "n" | "s" | "e" | "w"
<proc-call> :=  <uppercase-letter>
<proc-def>  :=  <uppercase-letter> "=" <program>

명령은 다섯 종류다.

• m("앞으로 이동")은 Karel이 바라보는 방향으로 한 칸 이동한다. 그 앞이 장애물이면 아무 일도 일어나지 않는다.
• l("왼쪽으로 회전")은 Karel을 왼쪽으로 90도 돌린다.
• X(X는 임의의 대문자)는 이름이 X인 프로시저를 호출한다.
• i("if")는 한 글자 조건과 괄호로 묶은 프로그램 두 개를 받는다. 조건이 성립하면 첫 번째 프로그램을 실행하고, 그렇지 않으면 두 번째 프로그램을 실행한다.
• u("until")는 한 글자 조건과 괄호로 묶은 프로그램 하나를 받는다. 조건이 성립하면 아무것도 하지 않는다. 그렇지 않으면 프로그램을 실행한 뒤 이 명령을 다시 반복한다.

조건은 b이거나, n, s, e, w 중 하나다. b는 Karel이 바라보는 방향의 바로 다음 칸에 장애물이 있을 때만 성립한다. n, s, e, w는 Karel이 각각 북, 남, 동, 서를 바라볼 때만 성립한다.

예를 들어 ub(m)은 "장애물을 만날 때까지 계속 앞으로 간다"는 뜻이고, un(l)은 "북쪽을 향하도록 돈다"는 뜻이다. 정의 R=lll은 오른쪽으로 도는 프로시저 R을 만든다.

첫 줄에 정수 r, c, d, e가 주어진다. r과 c(1 ≤ r, c ≤ 40)는 격자의 크기, d(0 ≤ d ≤ 26)는 프로시저 정의의 개수, e(1 ≤ e ≤ 10)는 실행할 프로그램의 개수다.

이어서 격자를 북에서 남으로 설명하는 r개의 줄이 주어진다. 각 줄은 서에서 동으로 c개의 문자로 이루어진다. 각 문자는 빈 칸을 뜻하는 '.'이거나 장애물을 뜻하는 '#'이다. 격자 바깥은 모두 장애물로 취급하므로 Karel은 격자를 벗어날 수 없다.

다음 d개의 줄은 각각 프로시저 정의다. 대문자 한 글자인 프로시저 이름과 그 본문이 주어진다. 같은 이름이 두 번 정의되지는 않는다. 본문에는 아직 정의되지 않은 프로시저를 호출하는 부분이 있을 수 있다.

마지막 2e개의 줄은 실행할 프로그램을 설명한다. 각 쌍은 두 줄로 이루어진다. 첫 줄에는 정수 i, j와 문자 h가 주어진다. i(1 ≤ i ≤ r)는 Karel의 시작 행, j(1 ≤ j ≤ c)는 시작 열이고, h ∈ {n, s, e, w}는 시작 방향이다. 시작 위치는 빈 칸임이 보장된다. 둘째 줄에는 그 시작 위치에서 실행할 프로그램이 주어진다.

모든 프로시저 본문과 실행할 프로그램은 길이가 1 이상 100 이하이며 문법적으로 올바르다. 정의된 프로시저만 호출한다. 정의와 프로그램이 적힌 줄에는 공백 문자가 없다.

각 프로그램에 대해, 시작 위치에서 프로그램 전체를 실행한 뒤 Karel의 최종 위치를 출력한다. 형식은 시작 위치와 같아서, 두 개의 숫자와 방향을 나타내는 문자 하나로 출력한다. 프로그램이 끝나지 않으면 대신 inf를 출력한다.