UVA589 Pushing Boxes

xht · 2025-09-17 16:40:40 · 题解

UVA589 Pushing Boxes

算法见其他题解，这篇题解主要是传播代码实现方式。

#include <bits/stdc++.h>
using namespace std;

#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", debug_out(__VA_ARGS__)
template <typename T> void debug_out(T t) { cerr << t << endl; }
template <typename T, typename... Ts> void debug_out(T t, Ts... ts) {
    cerr << t << ", ";
    debug_out(ts...);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    while (cin >> n >> m && n) {
        vector<vector<char>> a(n + 2, vector<char>(m + 2, '#'));
        vector<vector<vector<int>>> f(
            n + 2, vector<vector<int>>(m + 2, vector<int>(3, 1e9)));
        using S = tuple<int, int, int>;
        S st, ed;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                cin >> a[i][j];
                if (a[i][j] == 'X' && st == make_tuple(0, 0, 0)) {
                    st = {i, j, 0};
                    a[i][j] = '.';
                }
                if (a[i][j] == 'O') {
                    ed = {i, j, 0};
                    a[i][j] = '.';
                }
            }
        }
        {
            auto &[sx, sy, sz] = st;
            if (a[sx][sy + 1] == 'X') {
                sz = 1;
                a[sx][sy + 1] = '.';
            } else if (a[sx + 1][sy] == 'X') {
                sz = 2;
                a[sx + 1][sy] = '.';
            }
            f[sx][sy][sz] = 0;
        }
        queue<S> q;
        q.push(st);
        const int fx[3][4] = {{0, -2, 0, 1}, {0, -1, 0, 1}, {0, -1, 0, 2}};
        const int fy[3][4] = {{-2, 0, 1, 0}, {-1, 0, 2, 0}, {-1, 0, 1, 0}};
        const int fz[3][4] = {{1, 2, 1, 2}, {0, 1, 0, 1}, {2, 0, 2, 0}};
        auto check = [&](int x, int y, int z) {
            if (x < 1 || x > n || y < 1 || y > m) return 1;
            if (a[x][y] == '#') return 1;
            if (z == 0 && a[x][y] != '.') return 1;
            if (z == 1 && a[x][y + 1] == '#') return 1;
            if (z == 2 && a[x + 1][y] == '#') return 1;
            return 0;
        };
        while (!q.empty()) {
            if (ed == q.front()) break;
            auto [x, y, z] = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = x + fx[z][i], ny = y + fy[z][i], nz = fz[z][i];
                if (check(nx, ny, nz)) continue;
                if (f[nx][ny][nz] == 1e9) {
                    f[nx][ny][nz] = f[x][y][z] + 1;
                    q.push({nx, ny, nz});
                }
            }
        }
        {
            auto [ex, ey, ez] = ed;
            if (f[ex][ey][ez] != 1e9)
                cout << f[ex][ey][ez] << endl;
            else
                cout << "Impossible" << endl;
        }
    }
    return 0;
}