| 题目名称 | 60. 不听话的机器人 |
|---|---|
| 输入输出 | nrobot.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 BYVoid
于2008-07-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：22， 提交：70， 通过率：31.43% | ||||
 农场主 |
100 | 0.112 s | 0.68 MiB | C++ |
 Ezoi_XY |
100 | 0.227 s | 0.64 MiB | C++ |
 zys |
100 | 0.320 s | 0.65 MiB | C++ |
 ytrytr |
100 | 0.320 s | 76.71 MiB | C++ |
 ONCE AGAIN |
100 | 0.518 s | 1.14 MiB | C++ |
 wo shi 刘畅 |
100 | 0.533 s | 1.71 MiB | Pascal |
 BYVoid |
100 | 0.617 s | 0.58 MiB | Pascal |
 0 |
100 | 0.721 s | 0.76 MiB | C++ |
 HouJikan |
100 | 0.723 s | 76.70 MiB | C++ |
|
Ezoi_XY |
100 | 0.777 s | 76.70 MiB | C++ |
| 本题关联比赛 | |||
| 20091023练习题 | |||
| 夭寿的小练习 | |||
| 关于 不听话的机器人 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
HouJikan
2014-09-28 11:09
4楼
| ||||
|
回复 @HouJikan :
我程序老运行错误……不太明白阁下的做法，在下用阁下的程序来对拍，可是造的小数据中…我觉得很多都是阁下的错了… 比如 7 3 4 3 **..*.* ***.*** ..*..** ****.*. ..*..*. .***... **.*.** RIGHT FORWARD FORWARD 阁下给出的答案是2，但……难道不应该是1吗…  ？ 水中音
2014-09-25 11:35
3楼
| ||||
|
记忆化dp害人啊，不能用滚动数组
MMMMMMMMMMM 。。。把所有int改成short int才过QAQ  | ||||
|
诡异的题目描述
 QhelDIV
2013-04-10 11:42
1楼
| ||||
…-
题目描述
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
样例输出
1
样例说明
去掉第 3 条、第 5 条或者第 7 条指令都可以保证机器人无危险。
数据范围
迷宫的边长 N<=100。
指令数 M<=1000。
30%的数据M，N≤50