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

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

const int N=25;
int r,c;
char g[N][N];
struct S{
    int bx,by,px,py;
    string p;
    int ps,wk;
    S(int _bx,int _by,int _px,int _py,string _p,int _ps,int _wk):
        bx(_bx),by(_by),px(_px),py(_py),p(_p),ps(_ps),wk(_wk){}
    bool operator<(const S& o)const{
        if(ps!=o.ps)return ps>o.ps;
        if(wk!=o.wk)return wk>o.wk;
        return p>o.p;
    }
};

int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
char pd[4]={'N','S','W','E'};
char bd[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 sx,int sy,int ex,int ey,int bx,int by,string& pt){
    if(sx==ex&&sy==ey)
	{
        pt="";
        return 1;
    }
    bool vs[N][N]={0};
    queue<pair<pair<int,int>,string> > q;
    q.push({{sx,sy},""});
    vs[sx][sy]=1;
    while(!q.empty())
	{
        int x=q.front().first.first;
        int y=q.front().first.second;
        string cur=q.front().second;
        q.pop();
        if(x==ex&&y==ey)
		{
            pt=cur;
            return 1;
        }
        for(int i=0;i<4;i++)
		{
            int nx=x+dx[i],ny=y+dy[i];
            if(vld(nx,ny)&&!(nx==bx&&ny==by)&&!vs[nx][ny])
			{
                vs[nx][ny]=1;
                q.push({{nx,ny},cur+bd[i]});
            }
        }
    }
    return 0;
}
int main()
{
	freopen("pushing.in","r",stdin);
	freopen("pushing.out","w",stdout);
    int cs=1;
    while(cin>>r>>c,r||c)
	{
        int sx,sy,bx,by,tx,ty;
        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]='.';
            }
        }
        priority_queue<S> pq;
        bool vs[N][N][4]={0};
        string pt;
        bool ok=0;
        for(int i=0;i<4;i++)
		{
            int nx=bx+dx[i],ny=by+dy[i];
            if(vld(nx,ny))
			{
                string tmp;
                if(pbfs(sx,sy,nx,ny,bx,by,tmp)) pq.push(S(bx,by,nx,ny,tmp,0,tmp.size()));
            }
        }
        string ans="";
        while(!pq.empty())
		{
            S s=pq.top();
            pq.pop();
            if(s.bx==tx&&s.by==ty)
			{
                ans=s.p;
                ok=1;
                break;
            }
            for(int i=0;i<4;i++)
			{
                int nbx=s.bx+dx[i],nby=s.by+dy[i];
                int pbx=s.bx-dx[i],pby=s.by-dy[i];
                if(vld(nbx,nby)&&vld(pbx,pby))
				{
                    string tmp;
                    if(pbfs(s.px,s.py,pbx,pby,s.bx,s.by,tmp))
					{
                        int d;
                        if(dx[i]==-1&&dy[i]==0)d=0;
                        else if(dx[i]==1&&dy[i]==0)d=1;
                        else if(dx[i]==0&&dy[i]==-1)d=2;
                        else d=3;
                        if(!vs[nbx][nby][d])
						{
                            vs[nbx][nby][d]=1;
                            string np=s.p+tmp+pd[i];
                            pq.push(S(nbx,nby,s.bx,s.by,np,s.ps+1,s.wk+tmp.size()+1));
                        }
                    }
                }
            }
        }
        cout<<"Maze #"<<cs++<<endl;
        if(ok)cout<<ans<<endl<<endl;
        else cout<<"Impossible."<<endl<<endl;
    }
    return 0;
}