/ Vijos / 题库 /

Wappo

Wappo

描述

Einstein最近迷上了一款手机益智游戏Wappo,但是由于IQ和RP等诸多原因,他一直无法通关,他希望你编一个程序来玩这个游戏。

Wappo的游戏规则是这样的:在一张m*n的地图上,你可以控制勇士每秒向上下左右任意方向移动一格,之后怪兽会朝着你的方向移动至多两格。

注意,怪兽会优先横向走,勇士和怪兽都不会穿墙。

勇士的目的地就是桥头,但是千万不能被怪兽吃掉。

陷阱是很有用的东西(一格),勇士是不能进入陷阱的,但是如果你的IQ足够高,就可以把怪兽引入陷阱,在接下来你的三次移动中,怪兽将无法移动,三秒后恢复正常。

现在给你地图的信息,请你用最少的步数走到桥上。

格式

输入格式

第一行是两个正整数m,n(m,n<=20),表示地图的大小为m*n.
接下来是n行,每行m个整数,表示一个格子周围墙的信息。其中
1-上方有墙
2-左方有墙
4-右方有墙
8-下方有墙
例如,一个格子的左、上、右都有墙,那么代表这个格子的整数是2+1+4=7。

接下来是n行,每行m个字符,表示一个格子里的其他信息,其中
.-nothing
S-勇士的初始位置
W-陷阱
M-怪兽的初始位置
E-目的地,即桥头
其中S,M,E均保证只出现一次。

输出格式

输出包含若干行,前r行为最少步数走到桥头的走法,每行为up,down,left,right中的一个,表示勇士的走法。最后一行输出最少步数r,格式见样例。

若存在多解,按照上左右下的优先顺序行走。

若无法走到桥头,只输出一行impossible。

样例1

样例输入1

6 6
0  8  8  8  8  0
4  3  1  1  5  2
4  2  0  4  6  2
4  2  0  4  6  2
4 10  8  8 12  2
0  1  1  1  1  0
......
.S..W.
....M.
......
...E..
......

样例输出1

right
right
down
down
down
total steps: 5

限制

各点1s

提示

友情提示:怪兽掉进陷阱以后,如果没有走出来,不会继续掉进去。

来源

Mr.Roach原创

信息

ID
1044
难度
7
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
358
已通过
75
通过率
21%
上传者