题目描述

小汤姆非常喜欢玩游戏。有一天，他下载了一款名为“Bloxorz”的小型电脑游戏，这让他非常兴奋。这是一款关于在特殊平面上将盒子滚动到特定位置的游戏。具体来说，这个平面由多个单位格子组成，是一个矩形区域。盒子由两个完美对齐的单位立方体组成，可以平躺占据两个相邻的格子，或者直立占据一个单独的格子。玩家可以通过选择盒子在地面上的四个边之一，将盒子绕该边旋转90度来移动盒子，每次旋转算作一步。

平面上有三种格子：

1. 坚固的格子（'.'）：可以完全支撑盒子的重量，因此盒子可以平躺占据两个这样的格子，或者直立占据一个这样的格子。
2. 易碎的格子（'E'）：只能支撑盒子的一半重量，因此盒子不能直立占据单独一个这样的格子（必须平躺时至少有一个格子是坚固的）。
3. 空的格子（'#'）：无法支撑任何重量，盒子的任何部分都不能位于这样的格子上。

游戏的目标是以最少的步数将盒子滚动到平面上唯一的目标格子（'O'）上，并且盒子必须直立在该格子上。

盒子的状态

1. 直立状态：盒子占据一个单独的格子。

2. 平躺状态（水平）：盒子占据两个水平相邻的格子。

3. 平躺状态（垂直）：盒子占据两个垂直相邻的格子。
   

小汤姆在通过几个关卡后，发现游戏比他预想的要难得多，因此他向你求助。

输入格式

输入包含多个测试用例。每个测试用例代表游戏的一个关卡。

• 第一行是两个整数 $R$ 和 $C$（$3 \leq R, C \leq 500$），表示平面的行数和列数。
• 接下来的 $R$ 行，每行包含 $C$ 个字符，描述平面的布局：
  • 'O' 表示目标格子。
  • 'X' 表示盒子的初始位置（可能是一个 'X' 或两个相邻的 'X'）。
  • '.' 表示坚固的格子。
  • '#' 表示空的格子。
  • 'E' 表示易碎的格子。
• 输入以两个 0 结束。

保证条件：

1. 平面上只有一个 'O'。
2. 平面上要么有一个 'X'，要么有两个相邻的 'X'。
3. 第一行、最后一行、第一列和最后一列的所有格子都是 '#'（空的格子）。
4. 所有 'O' 和 'X' 所在的格子都是坚固的（即 '.'）。

输出格式

对于每个测试用例，输出一行：

• 如果能将盒子滚动到目标格子并直立，输出最少步数。
• 如果无法完成目标，输出 "Impossible"（不带引号）。

输入样例 1

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

输出样例 1

10

来源

POJ Monthly--2007.08.05, Rainer