#3202. 「BalticOI 2019 Day1」潜艇

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: StudyingFather

题目描述

译自 BalticOI 2019 Day1 T2. Nautilus

有一艘潜艇正在海洋中秘密航行。

海洋是一个 R \times C 的网格,其中 # 代表岛屿,. 代表水域,潜艇只能在水域中航行。

每分钟,潜艇会发出一个无线电信号,代表潜艇要航行的方向。方向由如下字母表示:北(N),东(E),南(S),西(W)。

现在监听者已经架设了一台拦截潜艇信号的雷达。在最近的 M 分钟,雷达收集到了 M 个信号,由一个长度为 M 的字符串表示,例如 WS?EE??。收集到的信号有些无法解码,用 ? 表示。

监听者并不知道潜艇最初的位置,但想要借助地图计算出潜艇的当前位置。请你帮助监听者计算出潜艇当前可能的位置共有几种。

输入格式

输入第一行包含三个整数 R,C,M

接下来 R 行,每行 C 个字符,描述海域地图。

最后一行是一个长度为 M 的字符串,代表了监听者监听到的信号。保证字符串中只含有 NESW? 这几种字符。

输出格式

输出一个整数:潜艇当前可能的位置有几种。

样例

样例输入

5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??

样例输出

22

数据范围与提示

各子任务的分值与数据规模如下:

子任务 1(29 分): 1 \leq R,C,M \leq 100 ,监听到的信号中没有 ?
子任务 2(37 分): 1 \leq R,C,M \leq 100
子任务 3(34 分): 1 \leq R,C \leq 500 1 \leq M \leq 5000