P13654 [CERC 2020] Excavation

警方调查发现，黑帮分子在城市地下布置了若干放射性石块，用以污染地下水。虽然已查明所有放射性石块的具体位置，但由于放射性的特殊性质，安全移除这些石块是一项极其困难的任务。因此，市政府决定使用带有防护装置的挖掘机将石块从地下取出。 城市的形状为一个正方形网格。市政部门拥有多种类型的挖掘机可供选择——Reepadlo、Qrtech、Bugger、Namakatschenko 和 Kopatsch。每种挖掘机具有不同的规格和移动方式。挖掘机的移动方式分别对应国际象棋中的车、后、象、马和王（见上图）。由于兼容性问题，每次只能部署一种类型的挖掘机。  每个网格最多只会有一块放射性石块。挖掘行动开始时，每块放射性石块的位置上各有一台挖掘机，并立即将该石块取出。接下来的操作必须严格遵守放射性安全处理协议。每一步操作中，只允许一台挖掘机执行一次移动，且该移动必须使挖掘机到达另一台挖掘机所在的位置。Reepadlo、Qrtech、Bugger 类型的挖掘机在一次跨越多个格子的移动过程中可以跳过其他挖掘机，即它们不必在遇到的第一台挖掘机处停下。挖掘机 $A$ 到达挖掘机 $B$ 的位置后，$B$ 会接管 $A$ 的负载，$A$ 随即退出行动并进行辐射清理。 如果最终只剩下一台挖掘机，则行动成功完成。也有可能无法成功完成该行动。 你的任务是判断该行动能否成功完成。如果可以，请输出实现该目标的挖掘机移动方案。

输入的第一行包含一个整数 $N$（$1 \leq N \leq 100$），表示城市的规模，以及一个字符，表示要部署的挖掘机类型（“R”——Reepadlo，“Q”——Qrtech，“B”——Bugger，“N”——Namakatschenko，“K”——Kopatsch）。 接下来有 $N$ 行描述城市中挖掘机的初始位置。每行包含 $N$ 个字符，每个字符要么是挖掘机类型的字母，要么是“.”表示该格为空。城市中至少有一台挖掘机。

输出的第一行若该配置可以成功完成行动，则输出“YES”，否则输出“NO”。如果可以成功完成行动，则接下来每行描述一次挖掘机的移动，按执行顺序输出。如果有多步操作，第 $i$ 行包含四个用空格分隔的整数 $X, Y, W, Z$（$1 \leq X, Y, W, Z \leq N$），表示有一台挖掘机从位置 $(X, Y)$ 移动到位置 $(W, Z)$。位置 $(X, Y)$ 表示第 $X$ 行（自上而下编号）第 $Y$ 列（自左至右编号）。

由 ChatGPT 4.1 翻译