比赛场次	46
比赛名称	20091023练习题
比赛状态	已结束比赛成绩
开始时间	2009-10-26 09:00:00
结束时间	2009-10-26 12:00:00
开放分组	全部用户
注释介绍

题目名称	不听话的机器人
输入输出	`nrobot.in/out`
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试点数	10 简单对比

用户	结果	得分
maxiem	AATTTTTTTT	20
.Xmz	WWWWWWWTTT	0
EnAsn	WWWWWWWWWW	0
打不死的羊	EEEEEEEEEE	0
bly1991	TTTTEEEEEE	0
Hamster	WWWWWWWWWT	0
Achilles	WWWWWWWWWT	0

不听话的机器人

★★ 输入文件：nrobot.in 输出文件：nrobot.out 简单对比
时间限制：1 s 内存限制：128 MiB

题目描述

DD 有一个不太听话的机器人，这个机器人总是会有自己的想法，而不会完全遵守 DD 给它的指令。

现在 DD 在试图命令机器人走迷宫。迷宫是一个 N*N 个格子组成的区域，格子自左上角到右下角从 (1,1) 到 (N,N) 编号。第 i 行、第 j 列的格子编号为 (i,j)。迷宫中的某些区域是障碍物，机器人不能移动到那里。

DD 给了机器人 M 条指令，指令的类型包括“前进一步”“后退一步”“左转九十度”“右转九十度”。但问题是机器人并不能完全遵守这些指令，因为如果机器人完全遵守这些指令，它可能会走到障碍物的格子里或者走到迷宫外面去，那样就会有危险。机器人希望从这个指令序列里面去掉一些，然后执行剩下的指令时，可以保证整个过程中都不会有危险。

机器人虽然不太听话，但它并不想惹恼了 DD，否则 DD 可能会把它拆掉的。所以机器人希望去掉的指令尽量少。

那么，机器人最少需要去掉多少条指令才能保证不会有危险呢？

输入格式

第一行有四个整数 N、M、X0、Y0。表示迷宫的大小是 N*N，指令共有 M 条，机器人初始时的位置是 (X0,Y0)。机器人初始时面朝的方向是上方。也就是说，若机器人按照初始时的方向走，效果是所在的 X 坐标越来越小。

下面有 N 行，每行有 N 个字符，可能是点号 '.' 或星号 '*'。'.' 表示空地，'*' 表示障碍。初始位置肯定是一个空地。

下面的 M 行，每行有一个字符串，表示指令。字符串可能是：FORWARD（前进一步）、BACK（后退一步）、LEFT（左转）、RIGHT（右转）。

输出格式

只需要输出一个整数，表示机器人最少需要去掉多少条指令才能保证不出危险。

样例输入

4 7 3 3

.***

..**

*..*

****

LEFT

FORWARD

LEFT

BACK

FORWARD

RIGHT

FORWARD

样例输出

样例说明

去掉第 3 条、第 5 条或者第 7 条指令都可以保证机器人无危险。

数据范围

迷宫的边长 N<=100。

指令数 M<=1000。

30%的数据M，N≤50