同样又得写170行的纯代码,还是十分不适应的QAQ.
优先我们得保证箱子的移动步数最小,然后我们得保证人的移动步数最少,再然后又得优先NSWE.
首先我们对箱子进行bfs,枚举方向的时候优先NSWE.然后取人步数最少的方案.
每次进行移动的时候对人进行bfs,bfs到的必定是最短距离,我们用seq存下它的移动次序.用于输出.
在最后输出的时候,我们直接先输出终点上个位子,然后输出人从某个点走到上个位子的花费,最后倒叙就好了QAQ
又到了艰难的写代码时刻//委屈委屈快哭了

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
const int N=25;
struct node
{
  int x,y,dir;//坐标+方向  
};
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int n,m;
char an[N][N];
bool st[N][N][4],used[N][N];
node pre[N][N][4];
int pre_man[N][N];
pi dis[N][N][4];
vector<int>path[N][N][4];//记录一下从哪个方向来到x,y的行程
bool ck(int x,int y)
{
    if(an[x][y]=='#'||x<0||x>=n||y<0||y>=m) return false;
    return true;
}

int bfs_man(pi man,pi tag,pi box,vector<int>&seq)
{
    memset(used,false,sizeof used);
    memset(pre_man,-1,sizeof pre_man);
    queue<pi>q;
    q.push(man);
    used[man.first][man.second]=true;
    used[box.first][box.second]=true;
    while(q.size())
    {
        pi t=q.front();
        q.pop();
        if(t==tag)
        {
            int x=t.first,y=t.second;
            while(pre_man[x][y]!=-1)
            {
                int d=pre_man[x][y];
                seq.push_back(d);
                x-=dx[d],y-=dy[d];
            }
            return seq.size();
        }
        for(int i=0;i<4;i++)
        {
            int x=t.first,y=t.second;
            int a=x+dx[i],b=y+dy[i];
            if(ck(a,b)&&!used[a][b])
            {
                used[a][b]=true;
                pre_man[a][b]=i;
                q.push({a,b});
            }
        }
    }
    return -1;
}

bool bfs_box(pi man,pi box,node &end)
{
    memset(st,false,sizeof st);
    queue<node>q;
    for(int i=0;i<4;i++)
    {
        int x=box.first,y=box.second;
        int j=x+dx[i],k=y+dy[i];//箱子要去的地方
        int a=x-dx[i],b=y-dy[i];//人要去的地方
        vector<int>seq;
        if(ck(a,b)&&ck(j,k)&&bfs_man(man,{a,b},box,seq)!=-1)//假如可行
        {
            st[j][k][i]=true;
            q.push({j,k,i});
            path[j][k][i]=seq;
            pre[j][k][i]={x,y,-1};
            dis[j][k][i]={1,seq.size()};
        }
    }
    bool flag=false;
    pi man_d={1e9,1e9};//把找到目标的代价置于无限大用于更新
    while(q.size())
    {
        node t=q.front();
        q.pop();
        if(an[t.x][t.y]=='T')
        {
            flag=true;
            if(dis[t.x][t.y][t.dir]<man_d)
            {
                man_d=dis[t.x][t.y][t.dir];
                end=t;
            }
        }
        for(int i=0;i<4;i++)
        {
            int x=t.x,y=t.y;
            int j=x+dx[i],k=y+dy[i];//箱子要去的地方
            int a=x-dx[i],b=y-dy[i];//人要去的地方
            vector<int>seq;
            if(ck(a,b)&&ck(j,k))
            {
                int distance=bfs_man({t.x-dx[t.dir],t.y-dy[t.dir]},{a,b},{x,y},seq);
                if(distance!=-1)
                {
                    pi &p=dis[j][k][i];
                    pi td={dis[t.x][t.y][t.dir].first+1,dis[t.x][t.y][t.dir].second+distance};
                    if(!st[j][k][i])
                    {
                        st[j][k][i]=true;
                        p=td;
                        q.push({j,k,i});
                        path[j][k][i]=seq;
                        pre[j][k][i]=t;
                    }
                    else if(p>td)
                    {
                        p=td;
                        path[j][k][i]=seq;
                        pre[j][k][i]=t;
                    }
                }
            }
        }
    }
    return flag;
}

int main()
{
    int T=1;
    while(cin>>n>>m,n||m)
    {
        for(int i=0;i<n;i++) cin>>an[i];
        pi box,man;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(an[i][j]=='S') man={i,j};
                else if(an[i][j]=='B') box={i,j};
            }
        }
        printf("Maze #%d\n",T++);
        node end;//记录终点路径
        if(!bfs_box(man,box,end)) puts("Impossible.");
        else
        {
            char ops[]="NSWE";
            string ans="";
            while(end.dir!=-1)
            {
                ans+=ops[end.dir];
                for(int i=0;i<path[end.x][end.y][end.dir].size();i++)
                {
                    int j=path[end.x][end.y][end.dir][i];
                    ans+=ops[j]+32;
                }
                end=pre[end.x][end.y][end.dir];
            }
            reverse(ans.begin(),ans.end());
            cout<<ans<<endl;
        }
        puts("");
    }
    return 0;
}

QAQ