记录编号	614716	评测结果	AA
题目名称	3488.[POJ 1475]推箱子	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	0.158 s
提交时间	2026-04-14 14:09:38	内存使用	3.39 MiB

#include <cstring>
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
const int cz[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const char cc[4] = {'n', 's', 'w', 'e'};
char g[25][25];
struct pos {
    int x, y;
    pos(int xx = 0, int yy = 0) {
        x = xx;
        y = yy;
    }
    bool operator==(const pos& yo) const& { return x == yo.x && y == yo.y; }
    bool operator!=(const pos& yo) const& { return x != yo.x || y != yo.y; }
};
struct node {
    pos p;
    int dir;
    int pc, bc;
    string ph;
    node(int xx, int yy, int dd, int pp, int bb, string pth) {
        p.x = xx;
        p.y = yy;
        dir = dd;
        pc = pp;
        bc = bb;
        ph = pth;
    }
    node(pos xx, int dd, int pp, int bb, string pth) {
        p = xx;
        dir = dd;
        pc = pp;
        bc = bb;
        ph = pth;
    }
    bool operator<(const node& yo) const& {
        if (bc != yo.bc) return bc > yo.bc;
        return pc > yo.pc;
    }
};
bool vis[25][25];
int r, c;
bool pd(pos x) {
    if (x.x >= 1 && x.y >= 1 && x.x <= r && x.y <= c && g[x.x][x.y] != '#') return 1;
    return 0;
}
/**
 *  @brief  查找人从 s 到 e 的最短方案, b 是箱子的初始位置.
 *  @param  s  人初始位置
 *  @param e 人目的位置
 *  @param b 箱子的初始位置
 */
string pbfs(pos s, pos e, pos b) {
    if (s == e) return "";
    memset(vis, 0, sizeof(vis));
    queue<pair<pos, string>> q;
    q.push(make_pair(s, ""));
    vis[s.x][s.y] = 1;
    while (!q.empty()) {
        pos u = q.front().first;
        string str = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            pos xx = pos(u.x + cz[i][0], u.y + cz[i][1]);
            if (pd(xx) && xx != b && !vis[xx.x][xx.y]) {
                q.push(make_pair(xx, str + cc[i]));
                vis[xx.x][xx.y] = 1;
                if (xx == e) return str + cc[i];
            }
        }
    }
    return "-1";
}
pair<int, int> dis[25][25][4];
/**
 *  @brief  查找箱子从 s 到 e 的最短方案, po 是人的初始位置.
 *  @param  s  箱子初始位置
 *  @param e 箱子目的位置
 *  @param po 人的初始位置
 */
string bbfs(pos s, pos e, pos po) {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<node> q;
    for (int i = 0; i < 4; i++) {
        pos xx = s;
        xx.x += cz[i][0];
        xx.y += cz[i][1];
        pos yy = s;
        yy.x -= cz[i][0];
        yy.y -= cz[i][1];
        string str = pbfs(po, yy, s);
        if (pd(xx) && pd(yy) && str != "-1") {
            q.push(node(xx, i, str.size(), 1, str + char(cc[i] - 32)));
            dis[xx.x][xx.y][i] = make_pair(1, str.size());
        }
    }
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if (make_pair(u.bc, u.pc) > dis[u.p.x][u.p.y][u.dir]) continue;
        if (u.p == e) return u.ph;
        pos po = u.p;
        po.x -= cz[u.dir][0];
        po.y -= cz[u.dir][1];
        for (int i = 0; i < 4; i++) {
            pos xx = u.p, yy = u.p;
            xx.x += cz[i][0];
            xx.y += cz[i][1];
            yy.x -= cz[i][0];
            yy.y -= cz[i][1];
            string str = pbfs(po, yy, u.p);
            if (pd(xx) && pd(yy) && str != "-1" &&
                make_pair(u.bc + 1, u.pc + (int)str.size()) < dis[xx.x][xx.y][i]) {
                q.push(node(xx, i, u.pc + str.size(), u.bc + 1, u.ph + str + char(cc[i] - 32)));
                dis[xx.x][xx.y][i] = make_pair(u.bc + 1, u.pc + str.size());
            }
        }
    }
    return "Impossible.";
}
int main() {
    int t = 0;
    while (true) {
        t++;
        cin >> r >> c;
        if (!(r && c)) return 0;
        pos s, e, b;
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                cin >> g[i][j];
                if (g[i][j] == 'B') {
                    b = pos(i, j);
                    g[i][j] = '.';
                }
                if (g[i][j] == 'S') {
                    s = pos(i, j);
                    g[i][j] = '.';
                }
                if (g[i][j] == 'T') {
                    e = pos(i, j);
                    g[i][j] = '.';
                }
            }
        }
        cout << "Maze #" << t << "\n" << bbfs(b, e, s) << endl << endl;
    }
}