机器人走迷宫

Time Limit: 1000 ms Memory Limit: 32768 KiB

Problem Description

迷宫对大家来说肯定是很熟悉的东西了,多数人都知道要想走出迷宫,在里面乱猜肯定是不行的,比较好的方法是贴着墙的一侧走,比如只贴着右侧走,最后肯定会走出迷宫,但不能保证要走多久,可能出口尽在咫尺你却错过了。

机器人只听从人的命令或按照预先写好的程序去行动。今天我们会给它命令,让它按照我们的命令去走,希望你能判断一下机器人能够走出迷宫,命令有四种:UDLR分别代表让机器人向上下左右四个方向移动,如果碰到墙则不移动。

Input

输入数据首先是地图,先给出HW分别代表地图的高和宽,然后是H*W的地图,*代表可以走,#代表墙,S代表起点,T代表终点。接下来是一个整数C代表命令的条数。接下一行有长度为C的字符串代表命令,0<=H,W<=10, 0<=C<=100

Output

如果机器人按照给定的命令走,能到达终点则输出Yes,否则输出No
注意:在命令执行完之前到达也算到达。

Sample Input

5 5
S****
####*
*****
**###
#***T
16
RRRRDDLLLLDRDRRR

Sample Output

Yes

Hint


Source

2011软件1-5班《程序设计基础》机试 tongjiantao