为您提供一个由 $$$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 的说明
下图显示了该示例的解决方案之一。