题意分析

1. 游戏背景：玩家需要在一个由单位方格组成的矩形平面上，将一个由两个单位立方体组成的箱子，通过滚动的方式移动到唯一的目标方格上。
2. 箱子状态：箱子有两种状态，一种是立着占据一个方格，另一种是躺着占据两个相邻的方格（水平或垂直方向）。
3. 移动规则：每次移动通过选取箱子与地面接触的四条边中的一条，将箱子围绕这条边旋转90度，计为一步。
4. 方格类型：
   • 坚固方格（.）：可以支撑箱子的全部重量，无论是箱子立着还是躺着时都可以作为支撑方格。
   • 易碎方格（E）：只能支撑箱子一半的重量，不能作为箱子立着时的唯一支撑方格。
   • 空方格（#）：不能支撑任何重量，箱子的任何部分都不能在该方格上。
5. 输入格式：
   • 输入包含多个测试用例，每个测试用例以两个整数 R 和 C（3 ≤ R, C ≤ 500）开始，表示平面的行数和列数。
   • 接下来 R 行，每行 C 个字符，表示平面的布局，其中 O 表示目标方格，X 表示箱子的初始位置。
   • 当输入 0 0 时，表示输入结束。
6. 输出格式：对于每个测试用例，输出最少的移动步数；如果无法到达目标方格，则输出 Impossible。

解题思路

1. 状态表示：使用结构体 Node 来表示箱子的状态，包括两个方格的坐标 (x1, y1) 和 (x2, y2) 以及当前的步数 step。
2. 广度优先搜索（BFS）：
   • 使用队列来存储箱子的状态，从初始状态开始进行BFS。
   • 对于每个状态，检查是否到达目标状态（两个方格都在目标位置 'O'），如果是，则返回当前步数。
   • 根据箱子的当前放置状态（立着、水平躺着、垂直躺着），计算出所有可能的下一步状态。
   • 对于每个可能的下一步状态，检查其是否合法（在地图范围内，不超出边界，不落在空单元格或无法承受重量的单元格上）。
   • 如果下一步状态合法且未被访问过，则将其加入队列，并标记为已访问。
3. 访问标记：使用三维数组 vis[x][y][k] 来记录箱子在位置 (x, y) 且处于某种状态 k（k = 0, 1, 2 分别表示水平躺着、垂直躺着、立着）是否已被访问过。

标准代码（C++）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

// 定义箱子状态结构体
struct Node {
    int x1, y1, x2, y2;
    int step;
    Node() {}
    Node(int a, int b, int c, int d, int e) : x1(a), y1(b), x2(c), y2(d), step(e) {}
};

int n, m;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  // 四个方向
char map[511][511];  // 存储地图
int vis[511][511][3];  // 记录状态是否访问过，第三维0:水平躺着，1:垂直躺着，2:立着
int sx1, sy1, sx2, sy2;  // 箱子初始位置
int nx1, ny1, nx2, ny2;  // 临时位置
Node start;  // 起始状态

// 检查新状态是否合法
bool check() {
    if (nx1 < 0 || nx1 >= n || nx2 < 0 || nx2 >= n ||
        ny1 < 0 || ny1 >= m || ny2 < 0 || ny2 >= m ||
        map[nx1][ny1] == '#' || map[nx2][ny2] == '#') return false;
    if (nx1 == nx2 && ny1 == ny2 && map[nx1][ny1] == 'E') return false;
    return true;
}

queue<Node> q;
// 处理新状态
void solve(int dir) {
    if (check()) {
        if (!vis[nx1][ny1][dir]) {
            vis[nx1][ny1][dir] = 1;
            q.push(Node(nx1, ny1, nx2, ny2, cur.step + 1));
        }
    }
}

// BFS算法
int spfa() {
    while (!q.empty()) q.pop();  // 清空队列
    memset(vis, 0, sizeof(vis));  // 初始化访问标记数组

    // 根据箱子初始状态标记起始状态已访问
    if (sx1 == sx2 && sy1 == sy2) vis[sx1][sy1][2] = 1;
    else if (sx1 + 1 == sx2) vis[sx1][sy1][1] = 1;
    else if (sy1 + 1 == sy2) vis[sx1][sy1][0] = 1;

    q.push(start);  // 将起始状态加入队列
    while (!q.empty()) {
        cur = q.front();  // 取出队首状态

        // 检查是否到达目标状态
        if (map[cur.x1][cur.y1] == 'O' && map[cur.x2][cur.y2] == 'O') return cur.step;

        q.pop();  // 弹出队首状态

        // 根据箱子当前状态计算下一步状态
        if (cur.x1 + 1 == cur.x2) {  // 垂直躺着
            ny1 = ny2 = cur.y1;
            nx1 = nx2 = cur.x1 - 1;
            solve(2);
            nx1 = nx2 = cur.x2 + 1;
            solve(2);
            nx1 = cur.x1, nx2 = cur.x2;
            ny1 = ny2 = cur.y1 - 1;
            solve(1);
            ny1 = ny2 = cur.y1 + 1;
            solve(1);
        } else if (cur.y1 + 1 == cur.y2) {  // 水平躺着
            nx1 = nx2 = cur.x1;
            ny1 = ny2 = cur.y1 - 1;
            solve(2);
            ny1 = ny2 = cur.y2 + 1;
            solve(2);
            ny1 = cur.y1, ny2 = cur.y2;
            nx1 = nx2 = cur.x1 - 1;
            solve(0);
            nx1 = nx2 = cur.x1 + 1;
            solve(0);
        } else {  // 立着
            for (int i = 0; i < 4; i++) {
                nx1 = cur.x1 + dir[i][0] + dir[i][0];
                ny1 = cur.y1 + dir[i][1] + dir[i][1];
                nx2 = cur.x2 + dir[i][0];
                ny2 = cur.y2 + dir[i][1];
                if (nx1 > nx2) swap(nx1, nx2);
                if (ny1 > ny2) swap(ny1, ny2);
                solve(i & 1);
            }
        }
    }
    return -1;  // 无法到达目标状态
}

int main() {
    while (~scanf("%d %d", &n, &m) && n && m) {
        sx1 = sy1 = sx2 = sy2 = -1;
        for (int i = 0; i < n; i++)
            scanf("%s", map[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'X') {
                    if (sx1 == -1) sx1 = i, sy1 = j;
                    else sx2 = i, sy2 = j;
                }
            }
        }
        if (sx2 == -1) sx2 = sx1, sy2 = sy1;
        start = Node(sx1, sy1, sx2, sy2, 0);  // 初始化起始状态

        int ans = spfa();
        if (ans == -1) printf("Impossible\n");
        else printf("%d\n", ans);
    }
    return 0;
}