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

#include<bits/stdc++.h>
using namespace std;
const int N=25;

struct Box{int bx,by,px,py;string p;};
struct Ps{int x,y;string p;};
int r,c,sx,sy,bx,by,tx,ty;
char g[N][N];
int bv[N][N][4];
int pv[N][N];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
char dc[4]={'n','s','w','e'};
char Dc[4]={'N','S','W','E'};
bool vld(int x,int y){return x>=0&&x<r&&y>=0&&y<c&&g[x][y]!='#';}
bool pbfs(int spx,int spy,int epx,int epy,int bbx,int bby){
    memset(pv,0,sizeof pv);
    queue<Ps> q;
    q.push({spx,spy,""});
    pv[spx][spy]=1;
    while(q.size()){
        Ps t=q.front();
        q.pop();
        if(t.x==epx&&t.y==epy){
            sx=t.x;
            sy=t.y;
            return 1;
        }
        for(int i=0;i<4;i++){
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(vld(nx,ny)&&!(nx==bbx&&ny==bby)&&!pv[nx][ny]){
                pv[nx][ny]=1;
                q.push({nx,ny,t.p+dc[i]});
            }
        }
    }
    return 0;
}
int main()
{
	freopen("pushing.in","r",stdin);
	freopen("pushing.out","w",stdout);
    int cs=1;
    while(cin>>r>>c,r||c)
	{
        for(int i=0;i<r;i++)
		{
            cin>>g[i];
            for(int j=0;j<c;j++)
            {
                if(g[i][j]=='S')sx=i,sy=j,g[i][j]='.';
                else if(g[i][j]=='B')bx=i,by=j,g[i][j]='.';
                else if(g[i][j]=='T')tx=i,ty=j,g[i][j]='.';
            }
        }
        memset(bv,0,sizeof bv);
        queue<Box> q;
        q.push({bx,by,sx,sy,""});
        bv[bx][by][0]=bv[bx][by][1]=bv[bx][by][2]=bv[bx][by][3]=1;
        string ans="";
        bool fnd=0;
        while(q.size())
		{
            Box t=q.front();
            q.pop();
            if(t.bx==tx&&t.by==ty)
			{
                ans=t.p;
                fnd=1;
                break;
            }
            for(int i=0;i<4;i++)
			{
                int nbx=t.bx+dx[i],nby=t.by+dy[i];
                int pbx=t.bx-dx[i],pby=t.by-dy[i];
                if(vld(nbx,nby)&&vld(pbx,pby))
				{
                    int st=t.px,sty=t.py;
                    g[t.bx][t.by]='#';
                    bool ok=pbfs(st,sty,pbx,pby,t.bx,t.by);
                    g[t.bx][t.by]='.';
                    if(ok&&!bv[nbx][nby][i])
					{
                        bv[nbx][nby][i]=1;
                        string np=t.p+ans.substr(0,ans.find_first_of("nswe")+1)+Dc[i];
                        q.push({nbx,nby,sx,sy,np});
                    }
                }
            }
        }
        cout<<"Maze #"<<cs++<<endl;
        if(fnd)cout<<ans<<endl<<endl;
        else cout<<"Impossible."<<endl<<endl;
    }
    return 0;
}