立体推箱子是一个风靡世界的小游戏。
游戏地图是一个N行M列的矩阵，每个位置可能是硬地（用”.”表示）、易碎地面（用”E”表示）、禁地（用”#”表示）、起点（用”X”表示）或终点（用”O”表示）。
你的任务是操作一个1×1×2的长方体。
这个长方体在地面上有两种放置形式，“立”在地面上（1×1的面接触地面）或者“躺”在地面上（1×2的面接触地面）。
在每一步操作中，可以按上下左右四个键之一。
按下按键之后，长方体向对应的方向沿着棱滚动90度。
任意时刻，长方体不能有任何部位接触禁地，并且不能立在易碎地面上。
字符”X”标识长方体的起始位置，地图上可能有一个”X”或者两个相邻的”X”。
地图上唯一的一个字符”O”标识目标位置。
求把长方体移动到目标位置（即立在”O”上）所需要的最少步数。
在移动过程中，”X”和”O”标识的位置都可以看作是硬地被利用。
输入格式
输入包含多组测试用例。
对于每个测试用例，第一行包括两个整数N和M。
接下来N行用来描述地图，每行包括M个字符，每个字符表示一块地面的具体状态。
当输入用例N=0，M=0时，表示输入终止，且该用例无需考虑。
输出格式
每个用例输出一个整数表示所需的最少步数，如果无解则输出”Impossible”。
每个结果占一行。
数据范围
3≤N,M≤5003≤N,M≤500
输入样例：
7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0
输出样例：
10算法：bfs
#include <iostream>
#include <cstdio>
#include <queue> using namespace std; const int maxn = 5e2+; struct rec {
int x, y, lie;
}; int n, m;
char Map[maxn][maxn];
int step[maxn][maxn][]; //存储步数
int dir[][] = {, -, , , -, , , }; //普通方向数组
//设0是立着，1是横着，2是竖着，这三种状态
int next_x[][] = {{, , -, }, {, , -, }, {, , -, }};
int next_y[][] = {{-, , , }, {-, , , }, {-, , , }};
int next_lie[][] = {{, , , }, {, , , }, {, , , }};
struct rec st, ed; //分别是起点和终点位置 bool valid(int x, int y) { //判断是否越界
if(x <= || x > n || y <= || y > m) {
return false;
}
return true;
} void parse_st_ed() { //找起点和终点
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
if(Map[i][j] == 'O') {
ed.x = i;
ed.y = j;
ed.lie = ;
Map[i][j] = '.';
}
if(Map[i][j] == 'X') {
for(int k = ; k < ; k++) {
int dx = dir[k][] + i;
int dy = dir[k][] + j;
if(valid(dx, dy) && Map[dx][dy] == 'X') {
st.x = min(dx, i);
st.y = min(dy, j);
st.lie = k < ? : ; //在dir数组里，0和1是左右，2和3是上下
Map[i][j] = Map[dx][dy] = '.';
break;
}
}
if(Map[i][j] == 'X') {
st.x = i;
st.y = j;
st.lie = ;
Map[i][j] = '.';
}
}
}
}
} bool check(rec next) {
if(!valid(next.x, next.y)) {
return false;
}
if(Map[next.x][next.y] == '#') {
return false;
}
//判断当前位置是否可行
if(next.lie == && Map[next.x][next.y] != '.') {
return false;
}
if(next.lie == && Map[next.x][next.y + ] == '#') {
return false;
}
if(next.lie == && Map[next.x + ][next.y] == '#') {
return false;
}
return true;
} int bfs() {
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
for(int k = ; k < ; k++) {
step[i][j][k] = -;
}
}
}
queue<rec> q;
step[st.x][st.y][st.lie] = ;
q.push(st);
while(!q.empty()) {
rec now = q.front();
q.pop();
for(int i = ; i < ; i++) {
rec next;
next.x = now.x + next_x[now.lie][i];
next.y = now.y + next_y[now.lie][i];
next.lie = next_lie[now.lie][i];
if(check(next) && step[next.x][next.y][next.lie] == -) {
step[next.x][next.y][next.lie] = step[now.x][now.y][now.lie] + ;
q.push(next);
if(next.x == ed.x && next.y == ed.y && next.lie == ed.lie) {
return step[next.x][next.y][next.lie];
}
}
}
}
return -; //无解
} int main() {
while(~scanf("%d %d", &n, &m)) {
if(n == && m == ) {
break;
}
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
cin >> Map[i][j];
}
}
parse_st_ed();
int ans = bfs();
if(ans != -) {
printf("%d\n", ans);
} else {
printf("Impossible\n");
}
} return ;
}