蒟蒻求助

#include <bits/stdc++.h>
#define ll long long
#define reg register
using namespace std;
const int dx[5] = { -1 , 1 , 0 , 0 , 0 };
const int dy[5] = {  0 , 0 ,-1 , 1 , 0 };
const int N = 24;
const int INF = 0x3f3f3f3f;

char Map[N][N];
int n,m,move_man[N][N][5],move_box[N][N][5];

struct pos{
	int x,y;
}manst,boxst,ed,last[N][N];

struct state{
	int x,y,dir;
}pre[N][N][5];

inline pos make_pos(int x,int y){
	pos a;
	a.x = x;
	a.y = y;
	return a;
}

inline state make_state(int x,int y,int dir){
	state a;
	a.x = x;
	a.y = y;
	a.dir = dir;
	return a;
}

inline bool check(int x,int y){
	if(x<0||x>=n||y<0||y>=m) return false;
	if(Map[x][y] == '#') return false;
	return true; 
}

inline int bfs(pos s,pos t,pos box){
	if(s.x==t.x&&s.y==t.y) return 0;
	queue<pos> q;
	int dis[N][N];
	memset(dis,-1,sizeof(dis));
	dis[s.x][s.y]=0;
	if(!q.empty()) q.pop();
	q.push(s);
	
	while(!q.empty()){
		pos p = q.front();q.pop();
		for(reg int i=0;i<4;++i){
			pos next=make_pos(p.x + dx[i] , p.y + dy[i]);
			if(!check(next.x , next.y)) continue;
			if(next.x==box.x&&next.y==box.y) continue;
			if(dis[next.x][next.y]!=-1) continue;
			
			dis[next.x][next.y] = dis[p.x][p.y] + 1;
			last[next.x][next.y] = make_pos(p.x , p.y);
			if(next.x==t.x&&next.y==t.y) return dis[t.x][t.y];
			q.push(next);
		}
	}
	return INF;
}

inline state BFS(){
	int flag = INF,MIN = INF;
	queue<state> q;
	while(!q.empty()) q.pop();
	int cnt = 0;
	for(reg int i=0;i<4;++i){
		if( !check(boxst.x + dx[i] , boxst.y + dy[i]) ) continue;
		if( !check(boxst.x - dx[i] , boxst.y - dy[i]) ) continue;
		state next=make_state(boxst.x + dx[i] , boxst.y + dy[i] , i);
		cnt = bfs(manst, make_pos(boxst.x - dx[i] , boxst.y - dy[i]) , boxst);
		if(cnt==INF) continue;
		move_man[next.x][next.y][next.dir] = cnt + 1;
		move_box[next.x][next.y][next.dir] = 1;
		pre[next.x][next.y][next.dir] = make_state(manst.x , manst.y , 4);
		q.push(next);
		if(next.x==ed.x&&next.y==ed.y) MIN=cnt+1,flag=1;
	}
	
	while(!q.empty()){
		state p = q.front();q.pop();
		if(move_box[p.x][p.y][p.dir]==flag) break;
		for(reg int i=0;i<4;++i){
			if( !check(p.x + dx[i] , p.y + dy[i]) ) continue;
			if( !check(p.x - dx[i] , p.y - dy[i]) ) continue;
			if(move_box[p.x + dx[i]][p.y + dy[i]][i] <= move_box[p.x][p.y][p.dir] && move_box[p.x + dx[i]][p.y + dy[i]][i]!=-1) continue;
			state next = make_state(p.x + dx[i] , p.y + dy[i] , i);
			cnt = bfs( make_pos(p.x - dx[p.dir] , p.y - dy[p.dir]) , make_pos(p.x - dx[i] , p.y - dy[i]) , make_pos(p.x , p.y) );
			if(cnt==INF) continue;
			
			if(move_man[next.x][next.y][next.dir]==-1||move_man[next.x][next.y][next.dir] > move_man[p.x][p.y][p.dir] + cnt + 1){
				move_man[next.x][next.y][next.dir] = move_man[p.x][p.y][p.dir] + cnt + 1;
				pre[next.x][next.y][next.dir] = make_state(p.x , p.y , p.dir);
			}
			if(move_box[next.x][next.y][next.dir]==-1){
				move_box[next.x][next.y][next.dir] = move_box[p.x][p.y][p.dir] + 1;
				q.push(next);
			}
			if(next.x==ed.x&&next.y==ed.y){
				MIN = min(MIN,move_man[next.x][next.y][next.dir]);
				flag = move_box[next.x][next.y][next.dir];
			}
		}
	}
	for(reg int i=0;i<4;++i){
		if(move_man[ed.x][ed.y][i]==MIN) return make_state(ed.x , ed.y , i);
	}
	return make_state(INF , 0 , 0);
}

void print2(pos res,pos next){
	if(next.x==res.x&&next.y==res.y) return;
	pos now = last[next.x][next.y];
	print2(res,now);
	if(now.x==next.x){
		if(next.y==now.y + 1) cout<<'e';
		else cout<<'w';
	}
	else{
		if(next.x==now.x + 1) cout<<'s';
		else cout<<'n';
	}
}

void print(state next){
	if(next.dir==4) return;
	state p=pre[next.x][next.y][next.dir];
	pos now = make_pos(p.x - dx[p.dir] , p.y - dy[p.dir]);
	pos nxt = make_pos(next.x - 2 * dx[next.dir] , next.y - 2 * dy[next.dir]);
	print(p);
	
	int cnt = bfs(now , nxt , make_pos(next.x - dx[next.dir] , next.y - dy[next.dir]));
	if(cnt!=INF&&cnt) print2(now , nxt);
	
	if(p.dir==4){
		if(boxst.x==next.x){
			if(next.y==boxst.y + 1) cout<<'E';
			else cout<<'W';
		}
		else{
			if(next.x==boxst.x + 1) cout<<'S';
			else cout<<'N';
		}
		return;
	}
	if(p.x==next.x){
		if(next.y==p.y + 1) cout<<'E';
		else cout<<'W';
	}
	else{
		if(next.x==p.x + 1) cout<<'S';
		else cout<<'N';
	}
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int cnt=0;
	while(cin>>n>>m&&n&&m){
		cnt++;
		memset(move_man,-1,sizeof(move_man));
		memset(move_box,-1,sizeof(move_box));
		for(reg int i=0;i<n;++i){
			for(reg int j=0;j<m;++j){
				cin>>Map[i][j];
				if(Map[i][j]=='S') manst = make_pos(i , j);
				else if(Map[i][j]=='B') boxst = make_pos(i , j);
				else if(Map[i][j]=='T') ed = make_pos(i , j);
			}
		}
		state ans = BFS();
		cout<<"Maze #"<<cnt<<'\n';
		if(ans.x==INF) cout<<"Impossible.";
		else print(ans);
		cout<<'\n';
	}	
	return 0;
}