描述
在蒙德和璃月的边界地带，有一个被遗忘的神庙，里面有一个奇怪的机关：滚动石碑。小熊必须操作这个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 竖2
int 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;
}