로봇

로봇은 $31 \times 31$ 크기의 판 위에서 진행하는 1인용 게임이다. 판은 $31$개의 행과 $31$개의 열로 이루어진 $1 \times 1$ 칸들로 나뉜다. 각 칸은 행 번호 $r$와 열 번호 $c$로 $(r, c)$와 같이 나타내며, 두 값 모두 $1$부터 시작한다. 한 칸은 비어 있거나, 당신이 있거나, 로봇이 있거나, 잔해가 놓여 있을 수 있다. 목표는 로봇에게 파괴되기 전에 모든 로봇을 파괴하는 것이다.

처음에 당신은 칸 $(15, 15)$에 있고, $(15, 15)$가 아닌 서로 다른 $R$개의 칸에 로봇 $R$대 $(1 \le R \le 50)$가 놓여 있다. 나머지 칸은 모두 비어 있다. 또한 순간이동 목적지가 될 수 있는 칸 $T$개 $(0 \le T \le 20)$의 목록이 주어진다. 당신이 먼저 움직이고, 그다음부터 당신과 로봇이 번갈아 움직인다.

당신의 차례에는 다음 중 정확히 하나만 할 수 있다.

• 여덟 방향(상하좌우와 대각선) 중 하나로 인접한 빈 칸으로 걸어간다.
• 잔해가 있는 인접한 칸으로 갈 때는, 같은 방향으로 그 잔해를 한 칸 더 밀어낸다. 단, 잔해가 밀려 들어갈 칸에 이미 다른 잔해가 있으면 안 된다. 그 칸에 로봇이 있으면 그 로봇은 파괴된다.
• 목록에 있는 목적지 중 하나로 순간이동한다. 목적지는 반드시 빈 칸이어야 한다.
• 제자리에 머문다.

당신이나 당신이 미는 잔해가 판 밖으로 나가게 되는 이동은 절대 할 수 없다.

로봇이 움직일 때, 각 로봇은 여덟 방향 중에서 당신의 현재 칸(즉 당신이 방금 이동한 뒤의 칸)에 가장 가까운 인접 칸으로 한 칸 이동한다. 이때 그 칸이 비어 있지 않아도 이동한다. 두 칸 $(r_1, c_1)$과 $(r_2, c_2)$ 사이의 거리는 $|r_1 - r_2| + |c_1 - c_2|$로 정의한다. 모든 로봇은 동시에 이동한다. 두 대 이상의 로봇이 같은 칸으로 이동하거나, 어떤 로봇이 이미 잔해가 있는 칸으로 이동하면, 그 로봇들은 모두 파괴된다. 파괴된 로봇은 잔해가 된다.

로봇이 당신의 현재 칸으로 이동하면 당신은 패배한다. 여러 로봇이 동시에 그 칸으로 와서 서로 파괴되더라도 마찬가지다. 모든 로봇이 파괴되었고 그중 어떤 로봇도 당신의 칸으로 이동하지 않았다면 당신은 승리한다.

가능한 한 오래 살아남기 위해, 당신은 즉시 패배(다음 당신 차례가 오기 전에 지는 것)로 이어지지 않는 이동만 고려한다. 전략은 다음과 같다. 당신의 이동과 뒤이은 로봇의 이동을 마친 뒤 남는 로봇의 수가 가장 적어지도록 걸어가거나 제자리에 머문다. 값이 같으면, 다음 당신 차례 직전에 도착 칸에서 남은 로봇까지의 최소 거리가 가장 커지는 이동을 고른다. 그래도 같으면 도착 칸의 행 번호가 가장 작은 이동을, 마지막으로 열 번호가 가장 작은 이동을 고른다.

걷거나 제자리에 머무는 어떤 이동으로도 즉시 패배를 피할 수 없으면, 목록을 항상 처음부터 훑어 아직 쓰지 않았고 즉시 패배로 이어지지 않는 첫 번째 유효한 목적지로 순간이동한다. 그런 목적지가 없으면 제자리에 머물러 패배한다.

이 전략을 구현하여 게임의 결과가 어떻게 되는지 출력하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 공백으로 구분된 두 정수 $R$와 $T$가 주어진다. 이어지는 $R$개의 줄에는 각 로봇의 시작 칸의 행과 열이 주어지며, 로봇들은 서로 다른 칸에서 시작하고 그중 어느 것도 $(15, 15)$가 아니다. 그다음 $T$개의 줄에는 순간이동 목적지의 행과 열이, 시도해야 하는 순서대로 주어진다. 입력은 $R = T = 0$인 테스트 케이스로 끝나며, 이 케이스는 처리하지 않는다.

각 테스트 케이스마다 케이스 번호를 한 줄에 다음 형식으로 출력한다(번호는 $1$부터 시작): Case k:.

순간이동을 할 때마다 다음 형식의 줄을 출력한다.

Move m: teleport to (r,c)

여기서 $m$은 이번 이동을 포함하여 지금까지 한 이동의 수이고, $(r,c)$는 순간이동 목적지이다.

그다음 결과를 출력한다. 승리한 경우 다음을 출력한다.

Won game after making m moves.
Final position: (r,c)
Number of cells with debris: d

여기서 $m$은 승리했을 때까지 한 이동의 수, $(r,c)$는 당신의 최종 위치, $d$는 잔해가 있는 칸의 수이다. $m = 1$일 때도 항상 "moves"라고 쓴다.

패배한 경우 다음을 출력한다.

Lost game after making m moves.
Final position: (r,c)
Number of cells with debris: d
Number of robots remaining: n

여기서 $m$은 패배했을 때까지 한 이동의 수, $(r,c)$는 당신이 파괴된 칸, $d$는 잔해가 있는 칸의 수, $n$은 남아 있는 로봇의 수이다. $m = 1$일 때도 항상 "moves"라고 쓴다.

연속한 테스트 케이스의 출력은 빈 줄로 구분한다.