题目描述

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

个箱子到目的地。

给定一张 N
行 M

列的地图，用字符 . 表示空地，字符 # 表示墙，字符 S 表示人的起始位置，字符 B 表示箱子的起始位置，字符 T 表示箱子的目标位置。

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

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

推箱子.jpg
输入格式

输入包含多个测试用例。

对于每个测试用例，第一行包括两个整数 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

减少了代码行数
也减少了缩进的层数

C++ 代码

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

const int N=25;
typedef pair<int,int> PII;
struct Node { int x,y,dir; };

int n,m;
char g[N][N];
Node pre[N][N][4];
vector<int> path[N][N][4];
PII dist[N][N][4];
int dx[4]= {1,-1,0,0}, dy[4]= {0,0,1,-1};
int pre_man[N][N];
bool st[N][N][4],used[N][N];

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

int bfs_man(PII start,PII target,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();

        if(t==target) {
            seq.clear();
            int x=t.first,y=t.second;
            while(pre_man[x][y]!=-1) {
                int dir=pre_man[x][y]^1;
                seq.push_back(dir);
                x+=dx[dir],y+=dy[dir];
            }
            return seq.size();
        }

        for(int ii=0; ii<4; ii++) {
            int i=ii^1;
            int a=t.first+dx[i],b=t.second+dy[i];
            if(!check(a,b) || used[a][b]) continue;

            used[a][b]=true;
            pre_man[a][b]=i;
            q.push({a,b});
        }
    }
    return -1;
}

bool bfs_box(PII man,PII box,Node &tar) { //tar:target
    memset(st,false,sizeof st);

    queue<Node> q;
    q.push({box.first,box.second,-1});
    bool kickoff=true;

    PII man_d= {1e9,1<<30};

    for(;q.size();kickoff=false) {
        auto t=q.front();
        q.pop();

        if(g[t.x][t.y]=='T' && dist[t.x][t.y][t.dir]<man_d) 
            man_d=dist[t.x][t.y][t.dir],    tar=t;

        for(int i=0; i<4; i++) {
            int a=t.x+dx[i],b=t.y+dy[i];
            int j=t.x-dx[i],k=t.y-dy[i];
            if(!check(a,b) || !check(j,k))continue;

            vector<int>seq;
            auto &p=dist[j][k][i];
            int steps;
            if(!kickoff)man={t.x+dx[t.dir],t.y+dy[t.dir]};
            steps=bfs_man(man, {a,b}, {t.x,t.y},seq);
            if(steps==-1) continue;

            PII td= {dist[t.x][t.y][t.dir].first+1,
                     dist[t.x][t.y][t.dir].second+steps };
            if(!st[j][k][i]) q.push({j,k,i});
            if(!st[j][k][i] || p>td) {
                p=td;
                path[j][k][i]=seq;
                pre[j][k][i]=t;
            }
            st[j][k][i]=true;
        }
    }
    return man_d.second < 1<<30;
}

int main() {
    int T=1;
    while(cin>>n>>m,n||m) {
        PII man,box;
        for(int i=0; i<n; i++){
            cin>>g[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};
        }
        printf("Maze #%d\n",T++);

        Node tar;

        if(!bfs_box(man,box,tar))
            puts("Impossible.");
        else {
            char mv[]="nswe";
            string res;
            while(tar.dir!=-1) {
                res+=mv[tar.dir]-32;
                for(auto dir:path[tar.x][tar.y][tar.dir])
                    res+=mv[dir];
                tar=pre[tar.x][tar.y][tar.dir];
            }
            reverse(res.begin(),res.end());
            cout<<res<<endl;
        }
        puts("");
    }
    return 0;
}