问题 D: 4、编程机器人(robot.pas/c/cpp)

问题 D: 4、编程机器人(robot.pas/c/cpp)

题目描述

  泽泽有一个可以编程的机器人,这个机器人处在二维的迷宫世界中。自从他参加了编程兴趣班后,他深深地迷上了编程,他想编一个程序帮助机器人走出迷宫。
迷宫里可能会有一些障碍,用字符’#’表示障碍(机器人是不能通过的)。用字符’.’表示空单元(机器人是可以行走的)。
这个机器人在迷宫中初始的位置用字符'S'表示。迷宫只有一个出口,出口的位置用字符'E'表示。这两个位置都是没有障碍的,也可以行走。
机器人只能执行向上、向下、向左、向右四个方向的移动指令。
当泽泽给机器人编程时,他输入了一串有0~3组成的字符串s,这4个数字分别对应4个方向的移动指令。机器人会严格按照泽泽的字符串组成的指令进行移动,直到找到出口。
如果移动指令导致机器人离开迷宫或碰到障碍物,那么机器人将会崩溃(表示本次失败)。如果机器人到达出口’E’,那么机器人将不再执行接下去的指令(恭喜成功一次)。
不幸的是,泽泽在调试机器人时忘记了每个数字对应方向的移动指令。所以他想知道每个数字对应不同的方向移动指令后,机器人到达出口的方法有多少种?

输入

第一行输入两个整数n和m,分别表示迷宫的行和列的大小。
接下来的n行,每行输入m个字符,表示迷宫里的情况。
迷宫中的位置是'.'、'#'、'S'或'E'。('S'和'E'各只有一个)
最后一行将输入一个字符串s,表示泽泽给机器人下达的移动指令。(字符串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

提示

【样例1解释】
只有一个有效的对应关系,其中’0’代表向下,’1’代表向左,’2’代表向上,’3’ 代表向右,有了这个对应关系,机器人按这串指令进行移动,先向右走了4步,再向下走了3步,然后向左走了1步,到达出口。
【数据范围约定】
对于30%的数据,保证字符串s中每个字符都是’0’。
对于100%的数据,保证2≤n,m≤50, 1≤| s |≤100, | s |表示字符串s的长度。


序号 标题 作者 发表时间 费用 订购数 操作