题目背景

译自 ROI 2016 Day1 T2. Экспериментальная робототехника

题目描述

鞑靼斯坦的各大学是教育机器人学领域的领先中心。为了推广这一方向，决定向中小学生提出一个有趣的实验——让机器人在有限空间内进行“生存实验”。

实验在一个大小为 $n \times m$ 的矩形场地上进行。在实验开始时，部分给定的格子中各放置一个尚未激活的机器人。在收到“开始”指令后，计时器启动，并在每秒开始时发出信号。在每次计时器信号发出后（但不超过 $T_{\max} = 10^9$ 秒），允许激活部分机器人。

场地中的每个格子被涂成四种颜色之一，机器人通过传感器可以识别这些颜色。颜色对应于从当前格子移动到相邻格子的方向——北、南、东或西。在每次计时器信号发出的那一刻，所有已激活的机器人同时按照当前所在格子的颜色所指的方向移动到相邻格子。颜色的分布方式保证了：机器人永远不会移动出场地边界之外。

为了避免损坏，禁止以可能导致机器人碰撞的方式激活机器人。“碰撞”指的是两台或以上已激活的机器人在同一个时刻出现在同一个格子中。如果发生碰撞，则实验被视为失败。注意：若两个机器人从相邻格子相向移动，并最终互换位置，这不算作碰撞。

若所有已激活的机器人能在场地上无限长时间内持续移动而不发生碰撞，则实验视为成功完成。实验的结果定义为：被激活机器人的数量。

请你编写一个程序，帮助学生根据场地描述及初始放置的机器人位置，确定实验可能达到的最大结果；若有需要，还要指出应当激活哪些机器人以及在什么时刻激活，以达到这一最优结果。

输入格式

第一行包含三个整数 $n$、$m$ 和 $g$，其中：

• $n, m$ —— 场地的行数（从北到南）与列数（从西到东），满足 $1 \le n, m \le 1000$；
• $g$ —— 一个标志变量，取值为 $1$ 或 $0$。若 $g = 1$，则要求输出具体的机器人激活方案；若 $g = 0$，则仅需输出最大结果。

接下来 $n$ 行，每行包含 $m$ 个字符，描述场地格子的颜色及初始是否有机器人。颜色由一个字母表示移动方向：

• N 或 n 表示北；
• S 或 s 表示南；
• E 或 e 表示东；
• W 或 w 表示西。

若该格子初始放置了机器人，则对应字母为大写；否则为小写。

输出格式

输出的第一行包含一个整数 $k$ —— 实验中可被激活的机器人最大数量。

如果输入中 $g = 1$，则在接下来的 $k$ 行中，每行输出三个整数 $r, c, t$：

• $r$ 表示行号（从北到南，$1 \le r \le n$）；
• $c$ 表示列号（从西到东，$1 \le c \le m$）；
• $t$ 表示激活该机器人的时刻（$1 \le t \le 10^9$）。

若存在多种可达到最大结果的激活策略，输出任意一种均可。

3 4 0
SSSS
EESW
ENWW

4

3 4 1
SSSS
EeSW
ENwW

4
2 3 2
3 2 1
3 4 1
2 1 2

4 4 1
essS
Eess
Snww
EeWN

5
1 4 9
2 1 4
4 3 3
4 1 2
4 4 7

提示

样例解释

在第一个示例中，可以通过选择合适的时刻激活任意四个机器人来实现最大结果。例如，位于格子 $(1, 1)$ 和 $(3, 1)$ 的机器人不能同时被激活。由于本测试中 $g = 0$，无需给出具体的激活方案。

在第二个示例中，给出的答案并非唯一。

在第三个示例中，位于格子 $(4, 1)$ 与 $(4, 3)$ 的机器人被激活后，可以在格子 $(4, 2)$ 与 $(4, 3)$ 之间无限次交换位置，而不会发生碰撞。

数据范围

子任务编号	分值	$n, m$	$g$	其他条件	必须通过的子任务
1	11	$1 \le n, m \le 10$	$g = 0$	每个格子中初始均有机器人
2	13	$1 \le n, m \le 100$			1
3				无额外条件	1, 2
4	23		$g = 1$		1–3
5	17	$1 \le n, m \le 1000$	$g = 0$
6	23		$g = 1$		1–5

翻译由 ChatGPT-5 完成