立体推箱子是一个风靡世界的小游戏。
游戏地图是一个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+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<rec> 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; }