我滚我滚我滚滚滚

Time Limit: 5000 ms Memory Limit: 65536 KiB

Problem Description

现有一块立方体,尺寸为1*1*2。有一个由很多个小方格组成的矩形。每个小方格的尺寸为1*1。小方格的质量分三个等级,一级的可以支撑立方体的全部重量,二级的只能支撑一半的重量,三级的不能承重。若超过承重的最大限度,小方格会被压坏。当立方体竖直站立时,它可在
压坏小方格的前提下,向前后左右四个方向滚动滚动后会平躺在相邻的两个小方格上。当立方体平躺时,也可在
压坏小方格的前提下向四个方向滚动,滚动后或平躺在相邻的两个方格上,或站立于相邻的一个方格上。
若下图所示:

此时,立方体竖直站立在一个小方格上。

此时,立方体的状态由上图中的立方体向前滚动所得。平躺在两个方格上。
 
现在在地图上有,‘X’,‘O’两点,‘X’表示开始时表示立方体竖直站立的位置。‘O’表示目标点。问在
压坏小方格且不滚出矩阵的前提下立方体最少要滚动多少次才能竖直站立在‘O’点。设
‘X’点和‘O’点的小方格质量均为一级。

Input

多组输入。每组输入中的第一行为两个整数n,m(5 <= n,m <= 600),表示矩阵有多少行和列。接下来的n行,每行有m个字符。‘.’表示质量为一的小方格,‘E’表示质量为二的小方格,‘#’表示质量为三的小方格。
 
输入数据保证:
1, 矩形中有且仅有一个‘O’点和一个‘X’点。
2, 矩形的边界由质量为三级的小方格组成。

Output

对于每组数据,若立方体能到达目标点,则输出最小的移动次数,否则输出 “Impossible”。

Sample Input

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

Sample Output

7

Hint

 

Source

zmx