스네이크 게임 시뮬레이션

예전 노키아 휴대폰에 들어 있던 스네이크 게임을 시뮬레이션한다.

판은 $15 \times 15$ 격자다. 각 칸은 공백, 문자 X, 문자 F 중 하나다. X는 뱀의 몸이고, 게임을 시작할 때 뱀은 같은 행에 가로로 붙어 있는 X 세 칸이다. 셋 중 가장 오른쪽 칸이 머리이며, 뱀은 오른쪽으로 움직인다. F는 먹이다. 뱀은 판 밖으로 나가지 않고 자기 몸에 부딪히지도 않으면서 먹이를 먹고 길어진다.

데이터 세트 하나는 U, D, L, R, O로만 이루어진 20글자 문자열이다. U는 위, D는 아래, L은 왼쪽, R은 오른쪽으로 방향을 바꾸고, O는 지금 방향을 그대로 쓴다. 글자 하나가 이동 한 번이다.

이동 한 번은 다음 순서로 처리한다.

1. 지금 방향으로 머리 옆에 있는 칸을 목표 칸으로 정한다.
2. 목표 칸이 판 안이고 먹이가 있으면 뱀이 한 칸 길어지고 꼬리는 제자리에 남는다. 그렇지 않으면 꼬리 칸을 뱀에서 뺀다.
3. 목표 칸이 판 밖이거나, 꼬리를 뺀 뒤에도 뱀이 차지한 칸이면 게임이 끝난다.
4. 아니면 머리를 목표 칸으로 옮긴다. 그 칸에 먹이가 있었으면 먹이를 없애고 먹은 개수를 1 늘린다.

게임이 끝나면 그 데이터 세트의 남은 글자는 처리하지 않는다.

데이터 세트마다 판은 입력으로 주어진 처음 상태에서 다시 시작한다.

첫 15줄은 $15 \times 15$ 격자다. 각 줄은 15글자이고, 줄 끝의 공백은 빠져 있을 수 있다. X는 정확히 세 칸이며 같은 행에 가로로 붙어 있다.

다음 줄에 데이터 세트의 개수 $T$가 주어진다. $T$는 1 이상이다.

이어지는 $T$개의 줄에는 각각 U, D, L, R, O로만 이루어진 20글자 문자열이 주어진다.

데이터 세트마다 한 줄을 출력한다. 게임이 끝났으면 GAME OVER를, 끝나지 않았으면 먹은 먹이 개수와 공백 하나와 pellets를 차례로 출력한다. 개수가 1일 때도 pellets라고 쓴다.

그 다음 15줄에 마지막 판을 출력한다. 뱀이 차지한 칸은 X, 남은 먹이는 F, 나머지는 공백이다. 뱀이 판 밖으로 나가서 게임이 끝났으면 머리는 판 밖에 있으므로 그리지 않는다.

데이터 세트 사이에는 빈 줄을 하나 넣는다.