← 返回题目列表

Codeforces · 908/B

B. 新年和越野车机器人

中文机器翻译题面 查看原题

Bob 对机器人进行了编程,使其能够在二维迷宫中导航。

迷宫有一些障碍。空单元格由字符“.”表示,其中障碍物由“#”表示。

迷宫中有一个机器人。其起始位置用字符“S”表示。这个位置没有任何障碍。迷宫中还有一个出口。其位置用字符“E”表示。这个位置没有任何障碍。

机器人只能向上、向左、向右或向下移动。

当鲍勃对机器人进行编程时,他写下了由数字 0 到 3(含)组成的一串数字。他希望每个数字对应一个不同的方向,机器人将遵循这些方向到达出口。不幸的是,他忘记了将方向实际分配给数字。

机器人将选择一些随机的数字映射到不同的方向。机器人会将不同的数字映射到不同的方向。然后,机器人将根据给定的字符串顺序和选择的映射遵循指令。如果指令导致机器人离开迷宫边缘或撞到障碍物,机器人就会崩溃并崩溃。如果机器人在任何时候到达出口,那么机器人将停止遵循任何进一步的指令。

Bob 在调试他的机器人时遇到问题,因此他想确定数字到引导机器人到达出口的方向的映射数量。

输入

输入的第一行将包含两个整数 n 和 m (2 ≤ n, m ≤ 50),表示迷宫的维度。

接下来的 n 行每行将包含 m 个字符,表示迷宫。

迷宫的每个字符都是“.”、“#”、“S”或“E”。

迷宫中将恰好有一个“S”和一个“E”。

最后一行将包含单个字符串 s (1 ≤ |s| ≤ 100) — 给机器人的指令。 s的每个字符都是0到3之间的数字。

输出

打印一个整数,即数字到引导机器人到达出口的方向的映射数量。

示例

输入 #1

5 6
.....#
S....#
.#....
.#....
...E..
333300012

输出 #1

1

输入 #2

6 6
......
......
..SE..
......
......
......
01232123212302123021

输出 #2

14

输入 #3

5 3
...
.S.
###
.E.
...
3

输出 #3

0

注意

对于第一个样本,唯一有效的映射是 $$0 \rightarrow D, 1 \rightarrow L, 2 \rightarrow U, 3 \rightarrow R$$,其中 D 向下,L 向左,U 向上,R 向右。