题目描述

推箱子游戏相信大家都不陌生，在本题中，你将控制一个人把1个箱子到目的地。

给定一张N行M列的地图，用字符”.”表示空地，字符”#”表示墙，字符”S”表示人的起始位置，字符”B”表示箱子的起始位置，字符”T”表示箱子的目标位置。

求一种移动方案，使箱子移动的次数最少，在此基础上再让人移动的总步数最少。

方案中使用大写的“EWSN”（东西南北）表示箱子的移动，使用小写的“ewsn”（东西南北）表示人的移动。

输入格式
输入包含多个测试用例。

对于每个测试用例，第一行包括两个整数N，M。

接下来N行，每行包括M个字符，用以描绘整个N行M列的地图。

当样例为N=0，M=0时，表示输入终止，且该样例无需处理。

输出格式
对于每个测试用例，第一行输出”Maze #”+测试用例的序号。

第二行输入一个字符串，表示推箱子的总体移动过程，若无解，则输出”Impossible.”。

每个测试用例输出结束后输出一个空行。

若有多条路线满足题目要求，则按照N、S、W、E的顺序优先选择箱子的移动方向（即先上下推，再左右推）。

在此前提下，再按照n、s、w、e的顺序优先选择人的移动方向（即先上下动，再左右动）。

数据范围
1≤N,M≤20

样例

输入样例：
1 7
SB....T
1 7
SB..#.T
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
8 4
....
.##.
.#..
.#..
.#.B
.##S
....
###T
0 0
输出样例：
Maze #1
EEEEE

Maze #2
Impossible.

Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN

Maze #4
swwwnnnnnneeesssSSS

宽搜

1.箱子移动次数最少
2.人移动次数最少
3.N、S、W、E的顺序优先选择箱子的移动方向（即先上下推，再左右推）
4.按照n、s、w、e的顺序优先选择人的移动方向（即先上下动，再左右动）

如果把箱子和人看做整体更新状态只能保证整体总步数最小，而题中首先要使箱子移动次数最小。

首先假设有一只手可以直接推箱子，每个格子之间仍然可以看做是权值为1的两个点，整个矩阵就一个无向图，可以bfs求最短路（宽搜的本质是迪杰斯特拉算法）

但是当箱子在某个点时，还要存储这个箱子是从哪个方向被推过来的，将箱子的位置和方向一起看做一个点，进行宽搜，再看人从上一个状态到这个状态最短路是多长，同样是宽搜。

在箱子的队列中，步数单调增加，但是，在箱子的步数增加1时，按照题目给出的顺序，不同的加1路径对应的人增加的步数不一定是单调增加的。但只要根据队列中的元素依次扩展节点，每次扩展都更新人的步数即可

一定要注意箱子和人的位置对方向的加减！注意状态的更新，不要漏记录某个值！

（最近的代码有的时候调试TLE，但是提交可以通过，不知道是不是出了bug -_-）

C++ 代码

#include<iostream>
#include<queue>
#include<cstring>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

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

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

int n,m;
char g[N][N];
Node pre[N][N][4];//存储箱子状态的前驱
vector<int>path[N][N][4];//人每个状态走的路径
bool st[N][N][4];//每个状态是否遍历过
PII dist[N][N][4];//存储到每个状态箱子的步数和人的步数
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}};//正常的上下左右
bool used[N][N];//在人走的路径宽搜时，防止走重复的路
int pre_man[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,0,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()){
        PII t=q.front();
        q.pop();
        if(t==end){//如果走到人的终点，记录路径
            seq.clear();
            int x=t.first,y=t.second;
            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 x=t.first,y=t.second;
            int a=x+d_d[i][0],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 man,PII 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 a=x+d[i][0],b=y+d[i][1];//人在这个位置把箱子推到(j,k)
        int j=x-d[i][0],k=y-d[i][1];//箱子推了之后到达的位置
        vector<int>seq;//人走的序列，seq的元素数量就是人走的步数
        if(check(a,b)&&check(j,k)&&bfs_man(man,{a,b},box,seq)!=-1){//如果人可以走过来推箱子
            st[j][k][i]=true;//推过来到达的这个状态置为已走过
            q.push({j,k,i});//i方向把箱子推到(j,k)
            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];//人在这个位置把箱子推到(j,k)
            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 man,box;//找到人和箱子的起点位置
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(g[i][j]=='S') man={i,j};
                else if(g[i][j]=='B') box={i,j};
            }
        }
        Node end;//可能从四个方向到达终点
        char ops[]="NSWE";
        if(!bfs_box(man,box,end))    cout<<"Impossible."<<endl;
        else{
            string res="";
            while(end.dir!=-1){
                res+=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];
                    res+=ops[j]+32;
                }
                end=pre[end.x][end.y][end.dir];
            }
            reverse(res.begin(),res.end());
            cout<<res<<endl;
        }
        cout<<endl;
    }
    return 0;
}