推箱子

要求（递减）
1 箱子走过路程最短
2 人走过路程最短
3 箱子优先按nswe走
4 人优先按nswe走

按照现实状态先考虑箱子怎么走，在此基础之上再想人怎么推
先bfs出箱子的最短路，然后在箱子的每一步中再bfs出人怎么推

箱子每次移动之后人总在箱子移动之前的位置上
把每次箱子移动后，人和箱子的位置看成一个状态

状态表示
( x, y, dir )
x y 为箱子的坐标 dir为人在箱子上下左右的哪个位置

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

typedef pair< int, int > PII;
const int N = 24;

struct Node
{
    int x;
    int y;
    int dir;
};

int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//往上推，人应该在下面
int d_d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//正常的上下左右
char ops[5] = "nswe";

int n,m;
char g[N][N];

//以箱子刚刚被推动之后为状态，如果人能够推动箱子，
//则人和箱子必定链接在一起组成一个长方形，
//用dir既代表人在箱子新坐标上下左右的哪一个位置上
//也可以表示出箱子旧坐标由哪个方向推到到新坐标

//箱子新坐标为(x,y)，人在箱子i方向，箱子是由i方向推过来的
//箱子旧坐标 == 人的新坐标
//为(x + d_d[i][0], y + d_d[i][1])

Node pre[N][N][4]; //存储箱子状态的前驱

int pre_man[N][N];//人由什么方向走来的
vector< int > path[N][N][4]; //人走的路径

PII dist[N][N][4];  //dist[j][k][i]表示箱子从初始坐标到坐标(j,k)人在箱子i方向时的箱子和人的最短路程
bool st[N][N][4],used[N][N];//标记箱/人

bool check( int x, int y )
{
    return x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '#';
}

//从起点到终点不经过箱子所需要的最少步骤
int bfs_man( PII start, PII end, PII box, vector<int>&seq )
{
    memset( used, false, sizeof used );
    memset( pre_man, -1, sizeof pre_man );

    queue< PII > q;
    q.push( start );

    used[start.first][start.second] = true;
    used[box.first][box.second] = true;  

    while( q.size() )
    {
        auto t = q.front();
        q.pop();

        int x = t.first;
        int y = t.second;

        if( t == end )
        {
            seq.clear();
            while( pre_man[x][y] != -1 )
            {
                int dd = pre_man[x][y];
                seq.push_back( dd );
                x += d[dd][0];
                y += d[dd][1];
            }
            return seq.size();
        }

        for( int i = 0; i < 4; i ++ )
        {
            int a = x + d_d[i][0];
            int b = y + d_d[i][1];
            if( check( a, b ) && !used[a][b])
            {
                used[a][b] = true;
                pre_man[a][b] = i;
                q.push( {a,b} );

            }
        }
    }
    return -1;
}

bool bfs_box( PII start, PII box, Node &end )
{
    memset( st, false, sizeof st );

    queue< Node > q;

    for( int i = 0; i < 4; i ++ )
    {
        int x = box.first;
        int y = box.second;

        int a = x + d[i][0];
        int b = y + d[i][1];//人的初位置

        int j = x - d[i][0];
        int k = y - d[i][1];//箱子的新位置

        vector <int> seq;
        if( check( a, b) && check ( j, k) && bfs_man( start, { a, b }, box, seq ) != -1)
        {
            st[j][k][i] = true;
            q.push( { j, k, i } );

            dist[j][k][i] = { 1, seq.size() };
            path[j][k][i] = seq;
            pre[j][k][i] = { x, y, -1};
        }
    }

    bool success=false;
    PII man_d={1e9,1e9};
    while(q.size()){
        Node t=q.front();
        q.pop();
        if(g[t.x][t.y]=='T')
        {
            success=true;

            if(dist[t.x][t.y][t.dir]<man_d){
                end=t;
                man_d=dist[t.x][t.y][t.dir];
            }
        }
        for(int i=0;i<4;i++)
        {
            int a=t.x+d[i][0],b=t.y+d[i][1];
            int j=t.x-d[i][0],k=t.y-d[i][1];
            if(check(a,b)&&check(j,k))
            {//人在的位置和箱子要去的位置是否能走
                PII &p=dist[j][k][i];//记录要到达的位置的距离的初始值，使用引用符，方便后面更新
                vector<int>seq;//人走的序列
                int distance=bfs_man({t.x+d[t.dir][0],t.y+d[t.dir][1]},{a,b},{t.x,t.y},seq);//注意这里人走的位置起点要从前一个的箱子位置还原
                if(distance!=-1){//可以走到
                    PII td={dist[t.x][t.y][t.dir].first+1,dist[t.x][t.y][t.dir].second+distance};//更新走到当前位置的距离
                    if(!st[j][k][i]){//如果没有到过这个状态
                        st[j][k][i]=true;
                        q.push({j,k,i});//将这个状态入队
                        path[j][k][i]=seq;//记录人具体的走的路径
                        pre[j][k][i]=t;//这个状态之前是什么状态，方便输出
                        p=td;//更新到达这个状态的距离
                    }
                    else if(p>td){
                        p=td;
                        path[j][k][i]=seq;
                        pre[j][k][i]=t;
                    }
                }
            }
        }
    }

    return success;
}


int main()
{
    int T = 1;
    while( cin >> n >> m, n || m )
    {

        for( int i = 0; i < n; i ++ )
            cin >> g[i];

        cout << "Maze #" << T << endl;
        T ++;

        PII start,box;
        for( int i = 0; i < n; i ++ )
            for( int j = 0; j < m; j ++ )
            {
                if( g[i][j] == 'S')
                    start = { i, j };
                else if( g[i][j] == 'B')
                    box = { i, j };
            }

        Node end;
        string res;
        if( !bfs_box( start, box, end ) ) 
             cout<<"Impossible."<<endl;
        else
        {
            while( end.dir != -1)
            {
                res += ops[end.dir] - 32;
                for( int i = 0; i < path[end.x][end.y][end.dir].size(); i ++ )
                {
                    int j = path[end.x][end.y][end.dir][i];
                    res += ops[j];
                }
                end = pre[end.x][end.y][end.dir];
            }
            reverse( res.begin(), res.end() );
            cout << res << endl;
        }
        cout << endl;
    }
}