CF254D Rats

老鼠已经在瓦西里·彼得罗维奇的商店地下室里繁殖到了成百上千只。瓦西里·彼得罗维奇也许还没有注意到它们的存在，但它们已经养成了潜入仓库偷食物的习惯。瓦西里·彼得罗维奇再也无法忍受了，他必须要消灭地下室里的老鼠。由于捕鼠器已经过时且没有作用，而老鼠药不仅会毒死老鼠还可能毒到粗心的人，他选择了一个激进的方法：在地下室里引爆两枚手榴弹（他没有更多的手榴弹）。 在本题中，我们用一个 $n \times m$ 的矩形表格来表示商店的地下室。表中的某些格子被墙壁占据，其余的格子为空。瓦西里已经观察到了老鼠们，并且发现它们会在某个时间入睡，而且每次都睡在相同的位置。他打算在这个合适的时间引爆手榴弹。在地下室的平面图上，他标记出了有睡着的老鼠的格子。显然，这些格子不可能被墙壁占据。 手榴弹只能在未被墙壁占据的格子中引爆。手榴弹的爆炸波传播规则如下。我们认为手榴弹在时刻 $0$ 爆炸。在初始时刻，仅有爆炸点上的格子会被“清理”。如果在时刻 $t$ 某个格子被清理，那么在时刻 $t+1$，所有与其相邻的非墙壁格子也会被清理（其中某些格子可能已被提前清理）。爆炸波会传播刚好 $d$ 秒，之后立即消失。  爆炸波分布的示例：图 1 展示了爆炸前的情形，后续的几幅图分别展示了在 $0,1,2,3,4$ 时刻被“清理”的格子。因此，图中的爆炸波传播时间为 $d=4$ 秒。瓦西里·彼得罗维奇想知道，他能否选择两个合适的位置引爆手榴弹，使得所有有睡着老鼠的格子都被清理。请编写程序判断能否做到，并给出解法。

第一行包含三个整数 $n$、$m$ 和 $d$，用单个空格分隔（$4 \leq n, m \leq 1000, 1 \leq d \leq 8$）。接下来的 $n$ 行每行包含 $m$ 个字符，表示地下室平面图。每行的每个字符含义如下： - “X” 表示该格子为墙壁。 - “.” 表示该格子为空。 - “R” 表示该格子为空，且有睡着的老鼠。 保证第一行和最后一行，以及第一列和最后一列全为“X”。平面图中至少有两个空格。至少有一个格子有睡着的老鼠。

如果无法通过两次爆炸清理所有有老鼠的格子，输出一个整数 $-1$。否则，输出四个整数 $r_1, c_1, r_2, c_2$，表示分别在 $(r_1, c_1)$ 和 $(r_2, c_2)$ 引爆手榴弹。 注意，行号从上到下为 $1$ 到 $n$，列号从左到右为 $1$ 到 $m$。$r_1, r_2$ 表示行号，$c_1, c_2$ 表示列号，且需满足 $1 \leq r_1, r_2 \leq n, 1 \leq c_1, c_2 \leq m$。禁止在同一格子内引爆两次手榴弹。两次爆炸的影响范围可以有交集。允许一种情况：某次爆炸什么老鼠也没清理，而另一颗手榴弹清理了所有老鼠。

由 ChatGPT 5 翻译