RC24#u3. 暖炉与水豚

暖炉与水豚

No testdata at current.

暖炉与水豚

PapiCon(@PapilloteContet)出了许多有意思的谜题,其中有一道关于水豚的谜题是这样的:

来源:x.com/PapilloteContet

在一个 N×M 的矩阵中有若干水豚以及暖炉,暖炉可以辐射以它自身为中心的 3×3 范围里的水豚,使其变得暖呼呼的。谜题里存在一只冷的要命的水豚,你需要移动其中的一个暖炉,使所有水豚都变得暖呼呼的。

在往下读题前,如果你有兴趣的话,不妨思考一下如何解答这个谜题。(思考结果与题目无关,可跳过。)

这个谜题的关键在于,单纯从图中能看到的暖炉来说是无解的,但如果注意到,第 3 行第 6 列的水豚明明周围没有暖炉,却也处于暖呼呼的状态,就能推测出来图中的那个对话框挡住了一个暖炉,只要移动这个暖炉就可以完成题目的要求。

现在我们将谜题一般化,对于给定的一个 N×M 的矩阵、对应的所有水豚状态、以及能看到的暖炉摆放情况,已知最多只有一只水豚的状态不太对劲(周围没有暖炉却暖呼呼的),你需要推测有哪些格子可能藏了暖炉。一个空格可能藏了暖炉可以理解为:当前空格设置暖炉后整个矩阵的状态会从不合法变为合法。

输入格式

输入第一行是两个正整数 N, M (1≤N,M≤1000),表示矩阵的大小。

接下来的 N 行,每行有 M 个字符,第 i 行的第 j 个字符表示矩阵中对应位置的状态,其中:

. 表示空格(或者说,看上去是空格的格子); c 表示很冷的水豚; w 表示暖呼呼的水豚; m 表示暖炉。

输出格式

输出若干行,每行两个正整数 r 和 c,表示第 r 行第 c 列有可能藏了一个暖炉,有多个可能时,先按 r 从小到大输出,r 相同时再按 c 从小到大输出。如果没有一个格子可能藏了暖炉, 则在一行中输出Too cold!

行与列均从 1 开始编号。

样例

6 8
wm....mw
.w..ww..
..wm.wwm
w.w....w
.m.c.m..
w.....w.
2 7
3 5
4 6
4 7