Description

这是一个关于将一个方块滚动到特定位置的游戏。准确地说，这个平面由几个单位单元格组成，是一个矩形形状的区域。而方块由两个完美对齐的单位立方体组成，可以躺下并占据两个相邻的单元格，也可以站立并占据一个单独的单元格。

你可以通过选择方块在地面上的四条边之一，并围绕该边旋转 90 度来移动方块，每次旋转算作一步。有三种类型的单元格，刚性单元格、易碎单元格和空单元格。

• 刚性单元格可以支撑方块的全部重量，因此可以是方块所占据的两个单元格中的任意一个，也可以是方块完全站立在上面的单元格。
• 易碎单元格只能支撑方块重量的一半，因此不能是方块完全站立在上面的唯一单元格。
• 空单元格无法支撑任何东西，因此方块不可能部分位于该单元格上。

游戏的目标是以最少的步数将站立的方块滚动到平面上唯一的目标单元格。

方块站在单个单元格上。

方块横躺在两个相邻的单元格上。

方块纵躺在两个相邻的单元格上。

在小汤姆通过游戏的几个阶段后，他发现比他预期的要难得多。因此，他求助于你的帮助。

Input Format

输入包含多个测试案例。

每个测试案例都是游戏的一个阶段。它以两个整数 $R$ 和 $C$ 开头，表示平面的行数和列数。

接下来是平面，其中包含 $R$ 行和每行的 $C$ 个字符，其中 O 表示目标单元格，X 表示方块的初始位置，. 表示刚性单元格，# 表示空单元格，E 表示易碎单元格。一个测试案例以两个 0 结束输入。

输入保证：

• 平面上只有一个 O。
• 平面上要么有一个 X，要么有相邻的两个 X。
• 第一行（和最后一行）（以及第一列和最后一列）必须是 #（空单元格）。
• O 和 X 覆盖的单元格都是刚性单元格。

Output Format

对于每个测试案例，输出一行表示移动的最小次数，或在无法达到目标单元格时输出 Impossible。

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

10

Hint

数据范围

对于所有的数据：$3 ≤ R，C ≤ 500$。

翻译

翻译来自于：ChatGPT。