记录编号	611725	评测结果	AA
题目名称	3488.[POJ 1475]推箱子	最终得分	100
用户昵称	2_16鸡扒拌面	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2026-02-03 15:39:58	内存使用	3.95 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn = 25;
int n, m;
char s[maxn][maxn];
int fMan[maxn][maxn][4], fBox[maxn][maxn][4];
int dirx[4] = {-1, 1, 0, 0}, diry[4] = {0, 0, -1, 1};

int lastMan[maxn][maxn];
struct node { int x, y, dir; } lastBox[maxn][maxn][4];

inline bool valid(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m && s[x][y] != '#'; }

int dis[maxn][maxn];
int bfsMan(int sx, int sy, int tx, int ty, int banx, int bany) {
	memset(dis, -1, sizeof(dis));
	queue<node> queM;
	dis[sx][sy] = 0; queM.push((node){sx, sy});
	while (!queM.empty()) {
		node cur = queM.front(); queM.pop();
		if (cur.x == tx && cur.y == ty) return dis[cur.x][cur.y];
		for (int k = 0; k < 4; k++) {
			int x = cur.x + dirx[k], y = cur.y + diry[k];
			if (!valid(x, y)) continue;
			if (dis[x][y] == -1 && (x != banx || y != bany)) {
				dis[x][y] = dis[cur.x][cur.y] + 1;
				lastMan[x][y] = k;
				queM.push((node){x, y});
			}
		}
	}
	return -1; 
}

inline int getDir(int dx, int dy) {
	if (dx == -1) return 0;
	else if (dx == 1) return 1;
	else if (dy == -1) return 2;
	else return 3;
}

char dir2strU[4] = {'N', 'S', 'W', 'E'}, dir2strL[4] = {'n', 's', 'w', 'e'};
void bfsBox() {
	memset(fMan, -1, sizeof(fMan));
	memset(fBox, -1, sizeof(fBox));
	queue<node> queB;
	int sx = 0, sy = 0, manx = 0, many = 0, usedDir[4] = {0, 0, 0, 0};
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (s[i][j] == 'S') manx = i, many = j;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (s[i][j] == 'B') {
		sx = i; sy = j;
		for (int k = 0; k < 4; k++) {
			int x = i - dirx[k], y = j - diry[k];
			if (!valid(x, y)) continue;
			int moveMan = bfsMan(manx, many, x, y, sx, sy);
			if (moveMan < 0) continue;
			usedDir[k] = 1;
			fMan[i][j][k] = moveMan; fBox[i][j][k] = 0;
			queB.push((node){i, j, k});
		}
	}
	while (!queB.empty()) {
		node cur = queB.front(); queB.pop();
		for (int k = 0; k < 4; k++) {
			int x = cur.x + dirx[k], y = cur.y + diry[k];
			if (!valid(x, y)) continue;
			int moveMan = bfsMan(cur.x - dirx[cur.dir], cur.y - diry[cur.dir], cur.x - dirx[k], cur.y - diry[k], cur.x, cur.y);
			if (moveMan < 0) continue;
			if (fBox[x][y][k] == -1) {
				fBox[x][y][k] = fBox[cur.x][cur.y][cur.dir] + 1;
				fMan[x][y][k] = fMan[cur.x][cur.y][cur.dir] + moveMan;
				lastBox[x][y][k] = cur;
				queB.push((node){x, y, k});
			} else if (fBox[x][y][k] == fBox[cur.x][cur.y][cur.dir] + 1) {
				if (fMan[cur.x][cur.y][cur.dir] + moveMan < fMan[x][y][k]) {
					fMan[x][y][k] = fMan[cur.x][cur.y][cur.dir] + moveMan;
					lastBox[x][y][k] = cur;
				}
			}
		}
	}
	int tx = 0, ty = 0, pos = -1;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (s[i][j] == 'T') tx = i, ty = j;
	for (int k = 0; k < 4; k++) if (fBox[tx][ty][k] >= 0) pos = k;
	if (pos < 0) { puts("Impossible."); return ; }
	for (int k = 0; k < 4; k++) if (fBox[tx][ty][k] >= 0)
		if (fBox[tx][ty][k] < fBox[tx][ty][pos]) pos = k;
		else if (fBox[tx][ty][k] == fBox[tx][ty][pos] && fMan[tx][ty][k] < fMan[tx][ty][pos]) pos = k;
	node cur = (node){tx, ty, pos}; string ans;
	while (cur.x != sx || cur.y != sy || !usedDir[cur.dir]) {
		int x = lastBox[cur.x][cur.y][cur.dir].x, y = lastBox[cur.x][cur.y][cur.dir].y;
		int dir = lastBox[cur.x][cur.y][cur.dir].dir, k = getDir(cur.x - x, cur.y - y);
		ans.push_back(dir2strU[k]);
		bfsMan(x - dirx[dir], y - diry[dir], x - dirx[k], y - diry[k], x, y);
		int tmpx = x - dirx[k], tmpy = y - diry[k];
		while (tmpx != x - dirx[dir] || tmpy != y - diry[dir]) {
			int tmpdir = lastMan[tmpx][tmpy];
			ans.push_back(dir2strL[tmpdir]);
			tmpx -= dirx[tmpdir]; tmpy -= diry[tmpdir];
		}
		cur = lastBox[cur.x][cur.y][cur.dir];
	}
	bfsMan(manx, many, cur.x - dirx[cur.dir], cur.y - diry[cur.dir], sx, sy);
	int tmpx = cur.x - dirx[cur.dir], tmpy = cur.y - diry[cur.dir];
	while (tmpx != manx || tmpy != many) {
		int tmpdir = lastMan[tmpx][tmpy];
		ans.push_back(dir2strL[tmpdir]);
		tmpx -= dirx[tmpdir]; tmpy -= diry[tmpdir];
	}
	reverse(ans.begin(), ans.end());
	printf("%s\n", ans.c_str());
}

int main() {
	freopen("pushing.in","r",stdin);
	freopen("pushing.out","w",stdout);
	for (int tc = 1;; tc++) {
		scanf("%d%d", &n, &m);
		if (!n && !m) break;
		for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
		printf("Maze #%d\n", tc);
		bfsBox(); puts("");	
	}
	return 0;
}