5820 - 勇士

勇士被困在了一张m*n的地图上,可以控制勇士每秒向上、下、左、右任意方向移动一格,之后怪兽会朝着勇士方向移动至多两格。注意怪兽会优先横着走,勇士和怪兽都不会穿墙。勇士的目的地是桥头,但是千万不能被怪兽吃掉。陷阱是很有用的东西(一格),勇士是不能进入陷阱的,但是可以把怪兽引入陷阱,在接下来的三次移动中,怪兽将无法移动,3秒后恢复正常。现在给出地图的信息,请用最少的步数走在桥上。

输入

第1行是2个正整数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”。

样例

输入

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 . .
. . . . . .

输出

right
right
down
down
down
total steps:5

提示

【数据规模】

对于30%的数据满足:n≤5,且没有墙。

对于60%的数据满足:n≤10,且没有陷阱。

对于100%的数据满足:n≤20。

来源

课课通

时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题