U307022 Bloxorz I

题目背景

[游戏链接](http://www.4399.com/flash/13071_1.htm)

题目描述

立体推箱子是一个风靡世界的小游戏。 游戏地图是一个$N$行 $M$ 列的矩阵,每个位置可能是硬地(用 `.` 表示)、易碎地面(用 `E` 表示)、禁地(用 `#` 表示)、起点(用 `X` 表示)或终点(用 `O` 表示)。 你的任务是操作一个 $1×1×2$ 的长方体。 这个长方体在地面上有两种放置形式,“立”在地面上($1×1$ 的面接触地面)或者“躺”在地面上($1×2$ 的面接触地面)。 在每一步操作中,可以按上下左右四个键之一。 按下按键之后,长方体向对应的方向沿着棱滚动 90 度。 任意时刻,长方体不能有任何部位接触禁地,并且不能立在易碎地面上。 字符 `X` 标识长方体的起始位置,地图上可能有一个 `X` 或者两个相邻的 `X`。 地图上唯一的一个字符 `O` 标识目标位置。 求把长方体移动到目标位置(即立在 `O` 上)所需要的最少步数。 在移动过程中,`X` 和 `O` 标识的位置都可以看作是硬地被利用。

输入格式

输入包含多组测试用例。 对于每个测试用例,第一行包括两个整数 $N$ 和 $M$。 接下来 N 行用来描述地图,每行包括 $M$ 个字符,每个字符表示一块地面的具体状态。 当输入用例 $N=0,M=0$ 时,表示输入终止,且该用例无需考虑。

输出格式

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

说明/提示

### 数据范围 $3≤N,M≤500$