AcWing-172-立体推箱子

问题

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

游戏地图是一个 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≤500

输入样例：

7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0

输出样例：

10

思路

• bfs

用（i, j, lie）三元组代表一个状态：

1. lie = 0 表示当前站立在 (i, j) 位置。
2. lie = 1 表示当前横躺着，左半边正方体落在 (i, j) 位置。
3. lie = 2 表示当前竖躺着，上半边正方体落在 (i, j) 位置。

并用数组 d[i][j][lie] 记录从其实状态到每个状态的最小步数，然后直接从起点位置开始广度优先搜索即可。

题解

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

using namespace std;
const int MAX = 505;
struct rec {
    int i, j, lie;
};

int next_i[3][4] = {{0, 1, 0, -2},
                    {0, 1, 0, -1},
                    {0, 2, 0, -1}};
int next_j[3][4] = {{1, 0, -2, 0},
                    {2, 0, -1, 0},
                    {1, 0, -1, 0}};
int next_lie[3][4] = {{1, 2, 1, 2},
                      {0, 1, 0, 1},
                      {2, 0, 2, 0}};
int n, m, d[MAX][MAX][3];
char g[MAX][MAX];
rec st, ed;
queue<rec> q;

bool valid(int i, int j) {
    if (i >= 0 && i < n && j >= 0 && j < m) return true;
    return false;
}

bool valid(rec t) {
    if (!valid(t.i, t.j)) return false;     //超出地图范围
    if (g[t.i][t.j] == '#') return false;   //走到禁地
    if (t.lie == 0 && g[t.i][t.j] == 'E') return false;  //站立在易碎地面
    if (t.lie == 1 && (t.j + 1 == m || g[t.i][t.j + 1] == '#')) return false;      //横躺右边部分超出地图
    if (t.lie == 2 && (t.i + 1 == m || g[t.i + 1][t.j] == '#')) return false;      //竖躺下边部分超出地图
    return true;
}

int bfs() {
    while (q.size()) q.pop();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k < 3; ++k) {
                d[i][j][k] = -1;
            }
        }
    }

    d[st.i][st.j][st.lie] = 0;
    q.push(st);
    while (q.size()) {
        rec now = q.front();
        q.pop();

        for (int k = 0; k < 4; ++k) {
            rec next;
            next.i = now.i + next_i[now.lie][k];
            next.j = now.j + next_j[now.lie][k];
            next.lie = next_lie[now.lie][k];

            if (!valid(next)) continue;
            if (d[next.i][next.j][next.lie] == -1) {  //尚未走过
                d[next.i][next.j][next.lie] = d[now.i][now.j][now.lie] + 1;
                if (next.i == ed.i && next.j == ed.j && next.lie == ed.lie) return d[next.i][next.j][next.lie];
                q.push(next);
            }
        }
    }

    return -1;
}

int main() {
    while (cin >> n >> m && n) {
        st.lie = -1;
        for (int i = 0; i < n; ++i) {
            scanf("%s", g[i]);
            for (int j = 0; j < m; ++j) {
                if (g[i][j] == 'X') {
                    if (st.lie == -1) {
                        st.i = i, st.j = j, st.lie = 0;
                        continue;
                    }
                    if (st.lie == 0 && st.i == i) {   //横向躺
                        st.lie = 1;
                    }
                    if (st.lie == 0 && st.j == j) {   //纵向躺
                        st.lie = 2;
                    }
                }
                if (g[i][j] == 'O') {
                    ed.i = i, ed.j = j, ed.lie = 0;
                    g[i][j] = '.';  //改为可以行走
                }
            }
        }

        int res = bfs();
        if (res == -1) puts("Impossible");
        else cout << res << endl;
    }

    return 0;
}