立体推箱子是一个风靡世界的小游戏。

游戏地图是一个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 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 5e2+7;struct rec {    int x, y, lie;};int n, m;char Map[maxn][maxn];int step[maxn][maxn][3];       //存储步数int dir[4][2] = {
   0, -1, 0, 1, -1, 0, 1, 0};     //普通方向数组//设0是立着，1是横着，2是竖着，这三种状态int next_x[3][4] = {
   {
   0, 0, -2, 1}, {
   0, 0, -1, 1}, {
   0, 0, -1, 2}};int next_y[3][4] = {
   {-2, 1, 0, 0}, {-1, 2, 0, 0}, {-1, 1, 0, 0}};int next_lie[3][4] = {
   {
   1, 1, 2, 2}, {
   0, 0, 1, 1}, {
   2, 2, 0, 0}}; struct rec st, ed;  //分别是起点和终点位置bool valid(int x, int y) {  //判断是否越界    if(x <= 0 || x > n || y <= 0 || y > m) {           return false;    }    return true;}void parse_st_ed() {    //找起点和终点    for(int i = 1; i <= n; i++) {        for(int j = 1; j <= m; j++) {            if(Map[i][j] == 'O') {                ed.x = i;                ed.y = j;                ed.lie = 0;                Map[i][j] = '.';            }            if(Map[i][j] == 'X') {                for(int k = 0; k < 4; k++) {                    int dx = dir[k][0] + i;                    int dy = dir[k][1] + j;                    if(valid(dx, dy) && Map[dx][dy] == 'X') {                        st.x = min(dx, i);                        st.y = min(dy, j);                        st.lie = k < 2 ? 1 : 2; //在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 = 0;                    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 == 0 && Map[next.x][next.y] != '.') {        return false;    }    if(next.lie == 1 && Map[next.x][next.y + 1] == '#') {        return false;    }    if(next.lie == 2 && Map[next.x + 1][next.y] == '#') {        return false;    }    return true;}int bfs() {    for(int i = 1; i <= n; i++) {        for(int j = 1; j <= m; j++) {            for(int k = 0; k < 3; k++) {                step[i][j][k] = -1;            }        }    }    queue
        
          q;    step[st.x][st.y][st.lie] = 0;    q.push(st);    while(!q.empty()) {        rec now = q.front();        q.pop();        for(int i = 0; i < 4; 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] == -1) {                step[next.x][next.y][next.lie] = step[now.x][now.y][now.lie] + 1;                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 -1;  //无解}int main() {    while(~scanf("%d %d", &n, &m)) {        if(n == 0 && m == 0) {            break;        }        for(int i = 1; i <= n; i++) {            for(int j = 1; j <= m; j++) {                cin >> Map[i][j];            }        }        parse_st_ed();        int ans = bfs();        if(ans != -1) {            printf("%d\n", ans);        } else {            printf("Impossible\n");        }    }        return 0;}