Description

国际行星制图中心（ICPC）使用探测车来探索其他行星的地表。众所周知，其他行星的地表是一块完美平整的矩形网格，可以均匀地离散划分。每个格点要么是平地（可以由探测车通行），要么是岩石（无法通行）。

:::align{center}

在 Paranal 天文台附近测试的火星探测车。
图片由 ESO/G. Hudepohl 拍摄，采用 CC BY-SA 4.0 许可，来源于 Wikimedia Commons :::

今天，最新的 Hornet 探测车即将发射。它将按照一种简单的算法来探索行星。探测车内部会维护一个 $direction$ 序列，即“北、东、南、西”这四个方向的任意一个排列。当探测车移动时，会依次检查这个 $direction$ 列表，选择第一个不会让其离开行星表面、也不会驶入岩石格的方向，然后朝该方向移动一格。

在两个连续的移动之间，探测车有可能被宇宙射线击中，使得其 $direction$ 序列变成另一个排列。ICPC 的科学家们记录了探测车的所有移动路径，但手工判断探测车的 $direction$ 序列是否发生变化、何时发生变化十分困难。给定探测车移动序列，请你计算，为了与实际移动路径一致，探测车的 $direction$ 序列最少可能发生了几次改变（被宇宙射线击中）。

Input Format

第一行输入两个整数 $r$ 和 $c$，其中 $r$（$1 \le r \le 200$）表示行星的行数，$c$（$1 \le c \le 200$）表示列数。行的编号自北至南，列的编号自西至东。

接下来的 $r$ 行，每行包含 $c$ 个字符，表示行星表面布局。每个字符是 #（岩石，不可通行）、.（平地，可通行）或 S（探测车起始位置，也为平地）。网格中恰好有且仅有一个 S。

紧接着输入一行字符串 $s$，每个字符均为 N、E、S 或 W，分别表示探测车实际的移动方向。$s$ 的长度在 1 到 10 000 之间（含），且所有移动都只能经过可通行的格子。

Output Format

输出一个整数，表示与探测车实际移动路径一致所需的最小宇宙射线击中次数（即 $direction$ 序列的最小变化次数）。

5 3
#..
...
...
...
.S.
NNEN

1

3 5
.###.
....#
.S...
NEESNS

0

3 3
...
...
S#.
NEESNNWWSENESS

4

Hint

样例 1 说明： 探测车的 $direction$ 序列可能如下：第一次移动时，可以是优先往北，也可以是优先往南再往北。需要注意的是第二种情况不能走南，因为会离开行星表面。第二次移动时，必须优先往北。第三次移动时，必须优先往东。第四次移动时，可以优先往北，也可以优先往东再往北。因此，只需在第二步和第三步之间被宇宙射线击中一次，使得其 $direction$ 序列从 N??? 变成 EN??（其中 ? 表示剩下的任意方向）。

样例 2 说明： 探测车一开始的 $direction$ 序列为 NESW，就可以不变地完成全部移动。

由 ChatGPT 5 翻译