|
|
|
|
描述 Description |
|
|
|
Einstein最近迷上了一款手机益智游戏Wappo，但是由于IQ和RP等诸多原因，他一直无法通关，他希望你编一个程序来玩这个游戏。
Wappo的游戏规则是这样的：在一张m*n的地图上，你可以控制勇士每秒向上下左右任意方向移动一格，之后怪兽会朝着你的方向移动至多两格。
注意，怪兽会优先横向走，勇士和怪兽都不会穿墙。
勇士的目的地就是桥头，但是千万不能被怪兽吃掉。
陷阱是很有用的东西（一格），勇士是不能进入陷阱的，但是如果你的IQ足够高，就可以把怪兽引入陷阱，在接下来你的三次移动中，怪兽将无法移动，三秒后恢复正常。
现在给你地图的信息，请你用最少的步数走到桥上。 |
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
第一行是两个正整数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均保证只出现一次。
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
输出包含若干行，前r行为最少步数走到桥头的走法，每行为up,down,left,right中的一个，表示勇士的走法。最后一行输出最少步数r，格式见样例。
若存在多解，按照上左右下的优先顺序行走。
若无法走到桥头，只输出一行impossible。 |
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
各点1s |
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1261 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
