include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
struct Node{
int x,y,lie;
};
int f[510][510][3],n,m;
char g[1000][1000];
bool check(int x,int y) {
if(x < 0 || x >= n || y < 0 || y >= m) return false;
return g[x][y] != ‘#’;
}
int bfs(Node Start,Node End) {
memset(f,-1,sizeof(f));
f[Start.x][Start.y][Start.lie] = 0;
queue[HTML_REMOVED] q;
q.push(Start);
int d[3][4][3] = {
{{-2,0,2},{0,1,1},{1,0,2},{0,-2,1}},//立着
{{-1,0,1},{0,2,0},{1,0,1},{0,-1,0}},//横着
{{-1,0,0},{0,1,2},{2,0,0},{0,-1,2}}//竖着
};
while(!q.empty()) {
Node t = q.front();
q.pop();
for(int i = 0; i < 4; i) {
Node next = {t.x + d[t.lie][i][0],t.y + d[t.lie][i][1],d[t.lie][i][2]};
int x = next.x,y = next.y;
if(!check(x,y)) continue;
if(next.lie == 0 && g[x][y] == ‘E’) continue;
if(next.lie == 1 && !check(x,y + 1)) continue;
if(next.lie == 2 && !check(x + 1,y)) continue;
if(f[x][y][next.lie] == -1) {
f[x][y][next.lie] = f[t.x][t.y][t.lie] + 1;
q.push(next);
}
}
}
return f[End.x][End.y][End.lie];
}
int main() {
while(cin >> n >> m) {
if(n == 0 && m == 0) break;
Node Start = {-1},End;
for(int i = 0; i < n; i)
for(int j = 0; j < m; j)
cin >> g[i][j];
for(int p = 0; p < n; p)
for(int q = 0; q < m; q++)
if(g[p][q] == ‘X’ && Start.x == -1) {
if(g[p][q + 1] == ‘X’) Start = {p,q,1};
else if(g[p + 1][q] == ‘X’) Start = {p,q,2};
else Start = {p,q,0};
}else if(g[p][q] == ‘O’) End = {p,q,0};
if(bfs(Start,End) == -1) cout << “Impossible\n”;
else cout << bfs(Start,End) << endl;
}
return 0;
}
11