描述

在蒙德和璃月的边界地带，有一个被遗忘的神庙，里面有一个奇怪的机关：滚动石碑。小熊必须操作这个1×1×2的长方体石碑，使其通过不同的地面环境，最终放置到神秘的符号“O”上，以解开通往宝藏的大门。

石碑可以有三种放置形式：

• 立在地面上（1×1的面接触地面）。
• 横躺在地面上（1×2的面接触地面），似乎是为了休息或避开某些地面的损害。
• 竖趟在地面上（1×2的面接触地面）

地图是一个N行M列的矩阵，代表着充满未知的遗迹内部：

• 正常的地面由“.”表示，平坦且安全。
• 易碎的地面用“E”标识，石碑不能以全部重量压在这种地面上，特别是立着时。
• 不能通过的地面用“#”表示，这可能是古代结界或坍塌的部分。
• 起点用“X”表示，石碑的初始位置。
• 终点由“O”标识，是需要将石碑立在其上的目标位置。

小熊通过上下左右四个方向键来控制石碑沿边缘滚动90°。在整个探索过程中，石碑不能碰到不可通过的地面，也不能在易碎地面上以1×1的面立着。

地图上的“X”可能标识一个或两个相邻的位置，显示石碑是初始时是立着还是躺着的状态。

小熊的任务是以最少的步数，将石碑正确地立在“O”上，揭开这片古老土地的秘密。

输入

输入包含多组测试用例。

对于每个测试用例，第一行包括两个整数N和M。

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

当输入用例N=0，M=0时，表示输入终止，且该用例无需考虑。

数据范围

3≤N,M≤500

输出

对于每个测试用例，输出一个整数，表示小熊将石碑从起点推到目标点所需的最少步数。如果石碑无法成功地被推至目标点，则输出"Impossible"。

每个测试用例的结果输出在单独的一行。

输入样例 1 

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

输出样例：

10

代码实现：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=510;
char area[N][N];
int dist[N][N][3];
int n,m;
struct stone
{//立0    横1    竖2int x,y,st;stone(int a,int b,int c){x=a,y=b,st=c;}stone():x(0),y(0),st(0){};
};
stone start,target;int dxyz[4][3][3]={//dxyz[i][st][x,y,st]{{-2,0,2},{-1,0,1},{-1,0,0}},//向上{{0,-2,1},{0,-1,0},{0,-1,2}},//向左{{1,0,2},{1,0,1},{2,0,0}},//向下{{0,1,1},{0,2,0},{0,1,2}}//向右};
stone movestone(stone &p,int i)
{int x=p.x+dxyz[i][p.st][0];int y=p.y+dxyz[i][p.st][1];int z=dxyz[i][p.st][2];return stone(x,y,z);
}
bool isInside(int i,int j)
{return (i>=0&&j>=0&&i<n&&j<m);
}
bool isValid(stone s)
{if(!isInside(s.x,s.y)||area[s.x][s.y]=='#')return false;if(s.st==1&&(!isInside(s.x,s.y+1)||area[s.x][s.y+1]=='#'))return false;if(s.st==2&&(!isInside(s.x+1,s.y)||area[s.x+1][s.y]=='#'))return false;if(s.st==0&&area[s.x][s.y]=='E')return false;return true;
}
bool isVisited(stone t)
{return dist[t.x][t.y][t.st]!=-1;
}
int bfs(stone& s)
{queue<stone> q;q.push(s);dist[s.x][s.y][s.st]=0;while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){stone p=movestone(t,i);if(!isValid(p))continue;if(!isVisited(p)){dist[p.x][p.y][p.st]=dist[t.x][t.y][t.st]+1;q.push(p);if(p.x==target.x&&p.y==target.y&&p.st==target.st)return dist[p.x][p.y][p.st];}}}return -1;
}
int main()
{while(cin>>n>>m&&n){memset(area,'#',sizeof area);memset(dist,-1,sizeof dist);for(int i=0;i<n;i++)cin>>area[i];for(int i=0;i<n;i++)for(int j=0;j<m;j++){char t=area[i][j];if(t=='X'){start.x=i,start.y=j,start.st=0;area[i][j]='.';if(area[i][j+1]=='X')start.st=1,area[i][j+1]='.';if(area[i+1][j]=='X')start.st=2,area[i+1][j]='.';}if(t=='O')target.x=i,target.y=j,target.st=0;}int res=bfs(start);if(res==-1)cout<<"Impossible"<<endl;else cout<<res<<endl;}return 0;
}