← 返回题目列表

Codeforces · 2045/M

M. 镜子迷宫

中文机器翻译题面 查看原题

为您提供一个由 $$$R$$$ 行(从北到南编号为 $$$1$$$ 到 $$$R$$$)和 $$$C$$$ 列(从西到东编号为 $$$1$$$ 到 $$$C$$$)的网格。该网格中的每个单元格都是相同大小的正方形。位于 $$$r$$$ 行和 $$$c$$$ 列的单元格表示为 $$$(r, c)$$$。每个单元格可以是空的,也可以在单元格的对角线上有一面镜子。每个镜子都由一条线段表示。如果镜子位于从单元格的西南角到东北角的对角线上,则输入 $$$1$$$;对于另一条对角线,则输入 $$$2$$$。

这些镜子遵循反射定律,即反射角等于入射角。形式上,对于 $$$1$$$ 型镜子,如果一束光来自单元的北、南、西或东,那么它将分别反射到单元的西、东、北和南。同样,对于 $$$2$$$ 类型的镜子,如果一束光来自单元的北、南、西或东,那么它将分别反射到单元的东、西、南和北。

您想要从网格外部放置激光,以便所有镜子都被激光束击中。有 $$$2 \cdot (R+C)$$$ 可能放置激光的位置:

- 从网格北侧的 $$$c$$$ 列,对于 $$$1 \leq c \leq C$$$,向南发射激光束;
- 从网格南边的 $$$c$$$ 列,对于 $$$1 \leq c \leq C$$$,向北发射激光束;
- 从网格东侧 $$$r$$$ 行,$$$1 \leq r \leq R$$$,向西发射激光束;和
- 从网格西侧 $$$r$$$ 行,$$$1 \leq r \leq R$$$,向东发射激光束。

确定激光的所有可能位置,使所有镜子都被激光束击中。

输入

第一行由两个整数 $$$R$$$ $$$C$$$ ($$$1 \leq R, C \leq 200$$$) 组成。

接下来的 $$$R$$$ 行均由长度为 $$$C$$$ 的字符串 $$$S_r$$$ 组成。字符串 $$$S_r$$$ 的第 $$$c$$$ 个字符表示单元格 $$$(r, c)$$$。每个字符都可以是 .如果单元格为空,/ 如果单元格类型为 $$$1$$$ 镜像,或 \ 如果单元格类型为 $$$2$$$ 镜像。网格中至少有一面镜子。

输出

输出一个整数,表示激光可能的位置数量,以便所有镜子都被激光束击中。将此数字表示为 $$$k$$$。

如果 $$$k > 0$$$,则输出 $$$k$$$ 空格分隔的字符串,表示激光的位置。每个字符串都包含一个字符,后面紧跟一个整数(不带任何空格)。该字符代表网格的一侧,如果将激光放在网格的北侧、南侧、东侧或西侧,则分别可以是 N、S、E 或 W。整数表示行/列号。您可以按任何顺序输出字符串。

示例

输入 #1

4 4
.//.
.\\.
.\/.
....

输出 #1

2
N3 W2

输入 #2

4 6
./..\.
.\...\
./../\
......

输出 #2

2
E3 S2

输入 #3

4 4
....
./\.
.\/.
....

输出 #3

0

注意

示例输入/输出 #1 的说明

下图显示了该示例的解决方案之一。

示例输入/输出#2 的说明

下图显示了该示例的解决方案之一。