P14273 [ROI 2014 Day1] 鲁滨逊与鳄鱼

**译自 [ROI 2014](https://neerc.ifmo.ru/school/archive/2013-2014.html) Day1 T2.** ***[Робинзон и крокодилы](https://neerc.ifmo.ru/school/archive/2013-2014/ru-olymp-roi-2014-statement-day1.pdf)***

鲁滨逊住在一个由 $n \times m$ 个方格组成的矩形小岛上。 有几只鳄鱼爬上了岛，在阳光下取暖并打起了盹。鲁滨逊想要在不惊动它们的情况下，把这些讨厌的邻居赶回水里。为此，他向正在打盹的鳄鱼们扔坚果。 岛上的每个格子中至多有一只鳄鱼。被坚果惊吓到的鳄鱼会沿着固定方向**笔直奔跑**，直到冲进水里为止。对于每只鳄鱼，已知它被吓到后奔跑的方向。鳄鱼的奔跑方向始终与岛的边界**平行**。 如果一只受惊的鳄鱼在奔跑途中撞上了另一只鳄鱼，两只鳄鱼都会被激怒，并立刻攻击鲁滨逊。因此，鲁滨逊必须谨慎选择投掷坚果的目标，确保被吓跑的鳄鱼前方的所有格子都是**空的**。 鲁滨逊在一只鳄鱼完全跑进水里之前，不会再扔下一颗新的坚果。 请你编写程序，计算鲁滨逊**最多**可以赶走多少只鳄鱼，而不会激怒它们。

第一行包含两个整数 $n$ 和 $m$ —— 分别表示岛的南北方向和东西方向的格子数量。 接下来的 $n$ 行，每行包含 $m$ 个字符，描述岛上当前的鳄鱼分布情况。 - 若格子为空，则用符号 `.` 表示； - 若格子中有一只鳄鱼，则用一个字母表示它的逃跑方向： - `N` —— 向北； - `S` —— 向南； - `E` —— 向东； - `W` —— 向西。

输出一个整数 —— 鲁滨逊最多能赶走而不激怒的鳄鱼数量。

### 样例解释 下图展示了第三个样例的情况： :::align{center}  ::: ### 数据范围 本题包含三个子任务，每个子任务对应一组测试数据。只有当该子任务的所有测试数据均通过时，才能获得对应分值。 | 子任务编号 | 分值 | 限制条件 | |:--:|:--:|:--:| | 1 | 30 | $1 \le n, m \le 30$ | | 2 | 30 | $1 \le n, m \le 500$ | | 3 | 40 | $1 \le n, m \le 2000$ |