/ Vijos / 题库 /

不听话的机器人

不听话的机器人

背景

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(右转)。

输出格式

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

样例1

样例输入1

4 7 3 3
.***
..**
*..*
****
LEFT
FORWARD
LEFT
BACK
FORWARD
RIGHT
FORWARD

样例输出1

1

限制

只有1s

提示

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

数据范围:
迷宫的边长 N<=100。

指令数 M<=1000。

来源

dd_engi大牛的题目~别的信息学网站上也有

信息

ID
1592
难度
6
分类
动态规划 点击显示
标签
(无)
递交数
424
已通过
113
通过率
27%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库