[AdditionalFile5394.zip](file://AdditionalFile5394.zip?type=additional_file)

#5394. 「ROI 2014 Day 1」鲁滨逊与鳄鱼

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

译自 ROI 2014 Day1 T2. Робинзон и крокодилы

鲁滨逊住在一个尺寸为 $n \times m$ 个格子的矩形岛屿上。

岛上爬来了几只鳄鱼，它们晒着太阳睡着了。鲁滨逊想赶走这些不受欢迎的邻居，但又不想弄出太大的动静。为此，他决定用坚果丢向这些熟睡的鳄鱼。

岛上的每个格子最多只有一只鳄鱼。被坚果吓到的鳄鱼会沿着直线快速逃跑，直到到达水边。每只鳄鱼被吓到后逃跑的方向是已知的，且这些方向都与岛屿的边平行。

如果一只被吓到的鳄鱼在逃跑途中撞到另一只鳄鱼，它们会变得愤怒并攻击鲁滨逊。因此，鲁滨逊必须小心选择目标鳄鱼，确保其逃跑路径上只有空荡荡的格子。

鲁滨逊只有在上一只鳄鱼逃到水边后，才会投掷下一个坚果。

你需要编写一个程序，计算鲁滨逊最多能赶走多少只鳄鱼，而不激怒它们。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $m$，分别表示岛屿从北到南和从西到东的尺寸。

接下来的 $n$ 行每行包含 $m$ 个字符，描述岛上鳄鱼的当前位置。如果某个格子为空，则用点号「.」表示；如果格子内有鳄鱼，则用字母表示该鳄鱼被吓到后逃跑的方向。方向用以下字母表示：

• 「N」：向北
• 「S」：向南
• 「E」：向东
• 「W」：向西

输出格式

输出文件应包含一个整数，表示鲁滨逊最多能赶走的鳄鱼数量，而不激怒它们。

样例 1

输入

1 5
WN.SE

输出

4

样例 2

输入

1 3
E.W

输出

0

样例 3

输入

3 4
.N.W
WWSS
EWEW

输出

4

在第三个样例中，可以通过特定顺序赶走 $4$ 只鳄鱼，而不激怒它们。

数据范围与提示

详细子任务附加限制及分值如下表所示：