#83. 立体推箱子

立体推箱子

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

立体推箱子是一个风靡世界的小游戏。

游戏地图是一个N\red{N}M\red{M}列的矩阵,每个位置可能是硬地(用”.\red{.}”表示)、易碎地面(用”E\red{E}”表示)、禁地(用”#\red{\#}”表示)、起点(用”X\red{X}”表示)或终点(用”O\red{O}”表示)。

你的任务是操作一个1×1×2\red{1×1×2}的长方体。

这个长方体在地面上有两种放置形式,“立”在地面上(1×1\red{1×1}的面接触地面)或者“躺”在地面上(1×2\red{1×2}的面接触地面)。

在每一步操作中,可以按上下左右四个键之一。

按下按键之后,长方体向对应的方向沿着棱滚动90\red{90}度。

任意时刻,长方体不能有任何部位接触禁地,并且不能立在易碎地面上。

字符”X\red{X}”标识长方体的起始位置,地图上可能有一个”X\red{X}”或者两个相邻的”X\red{X}”。

地图上唯一的一个字符”O\red{O}”标识目标位置。

求把长方体移动到目标位置(即立在”O\red{O}”上)所需要的最少步数。

在移动过程中,”X\red{X}”和”O\red{O}”标识的位置都可以看作是硬地被利用。

输入格式

输入包含多组测试用例。

对于每个测试用例,第一行包括两个整数N\red{N}M\red{M}

接下来N\red{N}行用来描述地图,每行包括M\red{M}个字符,每个字符表示一块地面的具体状态。

当输入用例N=0M=0\red{N=0,M=0}时,表示输入终止,且该用例无需考虑。

输出格式

每个用例输出一个整数表示所需的最少步数,如果无解则输出”Impossible”。

每个结果占一行。

样例

输入样例

7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0

输出样例

10

提示

3N,M500\red{3≤N,M≤500}

高中组测试

未参加
状态
已结束
规则
ACM/ICPC
题目
4
开始于
2022-4-7 15:45
结束于
2022-4-11 19:45
持续时间
100 小时
主持人
参赛人数
18