本题没有可用的提交语言。

题目描述

机器人游戏是一款单人游戏，在一个$31×31$的棋盘上进行。棋盘被划分为$1×1$的单元格，排列成$31$行$31$列。每个单元格由$(r,c)$索引，其中$r$是行号，$c$是列号（从$1$开始计数）。单元格可能处于以下四种状态之一：空置、被玩家占据、被机器人占据或被残骸占据。这个游戏的目的是通过移动来摧毁所有机器人，同时避免被机器人摧毁。

游戏开始时，玩家位于$(15,15)$单元格，有$R$个机器人（$1\leq R\leq50$）分布在$R$个不同的单元格（不包括$(15,15)$）。所有其他单元格初始为空。同时给出$T$个（$0\leq T\leq20$）可能传送位置的单元格列表。玩家先移动，然后机器人和玩家交替移动。

在玩家的移动阶段，允许以下操作：

• 向八个罗盘方向之一移动到相邻的空单元格
• 传送到指定的传送位置之一（目标单元格必须为空）
• 保持不动

玩家可以移动到包含残骸的相邻单元格，前提是能沿着移动方向将残骸推到下一个相邻单元格，且该单元格不包含其他残骸。如果被推的残骸撞上机器人，该机器人将被摧毁。玩家不能做出任何会使自己或推动的残骸移出棋盘的操作。

在机器人移动阶段，每个机器人会向八个罗盘方向之一的相邻单元格移动（即使该单元格不空），选择使目标单元格与玩家当前位置曼哈顿距离最短的方向移动。两个单元格$(r_1,c_1)$和$(r_2,c_2)$之间的曼哈顿距离定义为$|r_1 - r_2|+|c_1 - c_2|$。所有机器人在移动阶段同时移动。如果两个或多个机器人移动到同一单元格，或者机器人移动到包含残骸的单元格，所有这些机器人都会被摧毁。被摧毁的机器人会变成残骸。

如果有任何机器人移动到玩家当前位置（即使多个机器人因此相互摧毁），玩家输掉游戏。如果所有机器人都被摧毁且没有机器人移动到玩家位置，玩家赢得游戏。

为了尽可能延长游戏时间，玩家只会考虑不会导致立即失败（即在下次移动前失败）的移动。一个合理的策略是总是选择在玩家移动和机器人移动后（即在下次移动前）剩余机器人数量最少的移动。如果出现平局，选择使与剩余机器人的最小距离最大的移动。如果仍有平局，选择目标单元格行号最小的移动，最后再按列号最小来打破平局。

如果无法通过行走或保持不动来避免立即失败，玩家应该从传送位置列表中选择第一个未使用过的合法目的地进行传送，前提是该传送不会导致立即失败。搜索传送位置时总是从列表开头开始。如果没有可用的传送目的地，玩家将保持不动，导致立即失败。

在这个问题中，你将实现这个策略并观察它的效果。

输入格式

输入包含多个测试用例。每个测试用例的第一行包含两个用空格分隔的整数$R$和$T$。接下来是$R$行，每行包含两个用空格分隔的整数，表示$R$个机器人的初始行和列位置。可以保证每个机器人初始位置不是$(15,15)$且所有机器人位置互不相同。然后是$T$行，给出可用的传送目的地列表，每行包含传送目的地的行和列坐标，用空格分隔。输入以$R=T=0$的用例结束。

输出格式

对于每个测试用例，首先在一行中输出用例编号（从$1$开始），格式如样例输出所示。对于每次传送操作，输出一行格式如下：

Move m: teleport to (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"）。

4 0
17 18
13 18
8 12
10 12
4 0
17 17
13 17
13 13
17 13
3 3
17 18
13 18
5 31
15 16
16 15
3 7
0 0

输出样例

Case 1:
Won game after making 5 moves.
Final position: (14,16)
Number of cells with debris: 1

Case 2:
Lost game after making 2 moves.
Final position: (15,15)
Number of cells with debris: 1
Number of robots remaining: 0

Case 3:
Move 30: teleport to (16,15)
Move 58: teleport to (15,16)
Move 86: teleport to (3,7)
Lost game after making 114 moves. 
Final position: (1,29)
Number of cells with debris: 1
Number of robots remaining: 1

题目来源

北美东部中部地区2001年