ACW172

代码：

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define gc getchar()
#define pc(c) putchar(c)
using namespace std;
const int N=507,D=5;
int n,m,mp[N][N];
struct Q{
	int x,y,d,s;
	/*
	0:(x,y)
	1:(x,y)(---)
	2:(x,y)
	  (---)
	*/
};
int xx,xy,xd,ox,oy;
bool vst[N][N][D];
int dir[4][4][3]={
{{-2,0,2},{1,0,2},{0,-2,1},{0,1,1}},
{{0,-1,0},{-1,0,1},{0,2,0},{1,0,1}},
{{0,-1,2},{-1,0,0},{0,1,2},{2,0,0}}
};
int dirx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
inline int read(){
	register int t=0,f=1;
	register char c=gc;
	while(c!='-'&&(c<'0'||c>'9')) c=gc;
	if(c=='-') c=gc,f=-1;
	while(c>='0'&&c<='9') t=10*t+(c^48),c=gc;
	return f*t;
}
inline char readc(){
	register char c=gc;
	while(isspace(c)) c=gc;
	return c;
}
void write(int x){
	if(x<0) pc('-'),x=-x;
	if(x>=10) write(x/10);
    pc((x%10)|48);
}
bool inmap(int x,int y){
	return x>=1&&x<=n&&y>=1&&y<=m;
}
bool ok(Q q){
	int x=q.x,y=q.y,d=q.d;
	if(!inmap(x,y)){
		return 0;
	}
	if(vst[x][y][d]){
		return 0;
	}
	if(mp[x][y]=='#'){
		return 0;
	}
	switch(d){
		case 0:{
			if(mp[x][y]=='E'){
				return 0;
			}
			break;
		}
		case 1:{
			if(mp[x][y+1]=='#'){
				return 0;
			}
			break;
		}
		case 2:{
			if(mp[x+1][y]=='#'){
				return 0;
			}
			break;
		}
	}
	return 1;
}
bool solve(){
	queue<Q> q;
	n=read(),
	m=read();
	if(!n&&!m) return 0;
	xx=xy=xd=ox=oy=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			mp[i][j]=readc();
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(mp[i][j]=='X'){
				xx=i,xy=j;
				for(int ii=0;ii<4;++ii){
					int tx=xx+dirx[ii][0],ty=xy+dirx[ii][1];
					if(inmap(tx,ty)&&mp[tx][ty]=='X'){
						mp[tx][ty]='.';
						xx=min(xx,tx),xy=min(xy,ty);
						if(ii==0||ii==1){
							xd=2;
						}
						else{
							xd=1;
						}
					}
					/*did not find:xd=0;*/
				}
				mp[i][j]='.';
			}
			if(mp[i][j]=='O'){
				ox=i,oy=j;
				mp[i][j]='.';
			}
		}
	}
	q.push(Q{xx,xy,xd,0});
	memset(vst,0,sizeof vst);
	while(!q.empty()){
		Q qt=q.front(),qnew;
		vst[qt.x][qt.y][qt.d]=1;
		q.pop();
		int tx,ty,td;
		for(int i=0;i<4;++i){
			tx=qt.x+dir[qt.d][i][0],
			ty=qt.y+dir[qt.d][i][1],
			td=dir[qt.d][i][2];
			qnew=Q{tx,ty,td,qt.s+1};
			if(ok(qnew)){
				q.push(qnew);
				if(tx==ox&&ty==oy&&td==0){
					write(qnew.s),puts("");
					return 1;
				}
			}
		}
	}
	puts("Impossible");
	return 1;
}
signed main(){
	while(solve());
	return 0;
}