问题 26633 --G. 翻箱子

26633: G. 翻箱子

时间限制: 1 Sec  内存限制: 128 MB
提交: 27  解决: 11
[提交][状态][讨论版][命题人:]

题目描述

丁丁最近喜欢玩一种小游戏,叫翻箱子,玩得非常着迷,可时当当却笑他说这个游戏很久很久以前他就玩过并且早就通关了,这让丁丁好不爽,他也想马上通关,你能帮帮他吗?这个游戏有很多关,每一关都是一个地图,箱子是1×2×1大小的,如果箱子是平躺的,那么箱子可以往前或往后滚动,或者在两端竖起来,如果箱子是竖起来的,它可以往四方向倒下,目标就是使箱子竖着到达地图上有坑的地方,这样才能进入下一局,箱子只能全部在白色的格子中翻动,只要有一部分不在白色格子,游戏将失败。如下图,第一张图是开局图,第二张图是箱子往右倒下的图,第三张图是箱子往下滚动的图,第四张图是经过若干步骤后到达的位置,下一步,只要把箱子立起来,就能够让箱子到达目标坑位,进入下一关卡。

输入

输入包含多组地图数据,每组数组第一行是两个正数MN (<100),接着是M行字符,每行有N个字符,其中字符“#”表示不可到达,“.”表示白色格子,“H”表示目标坑位,“X”表示箱子的起始位置。


输出

对于每组输入,输出箱子最快到达目标坑位的移动步数,如果不能到达目标坑位,则输出no way

样例输入

4 4
####
#.H#
#XX#
####
5 5
#####
#...#
#X..#
#H..#
#####

样例输出

no way
3

来源

 

[提交][状态]