AcWing-174-推箱子

问题

推箱子游戏相信大家都不陌生，在本题中，你将控制一个人把 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

思路

• bfs

从箱子的当前位置开始出发进行 bfs，在确定箱子的移动方向后，再 bfs 出人从当前状态的位置移动到箱子移动的反方向的下一个距离位置的最短路径。箱子到达终点后更新最优结果即可。

注意 ，此题的最终结果是求最短箱子的位移距离，箱子移动相同情况下，再看人移动最小的距离。所以，当箱子第一次到达终点，不可以直接结束搜索（只能跳过本节点向后搜索的情况，即剪枝），后面可能会出现和当前箱子距离相同，但人的移动距离还要小的情况。

题解

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;
const int INF = 0x3fffffff, N = 25;
typedef long long ll;
char A[4] = {'N', 'S', 'W', 'E'};
char a[4] = {'n', 's', 'w', 'e'};
int r, c, num = 0;
int dir[4][2] = {{-1, 0},
                 {1,  0},
                 {0,  -1},
                 {0,  1}};
char s[N][N];
string tmp;

struct P {
    int x, y, px, py;
    string ans;

    P() {};
};

bool pd(int i, int j) {
    if (i >= 0 && i < r && j >= 0 && j < c && s[i][j] != '#') return true;
    return false;
}

bool bfs2(P p1, P p2) {
    tmp = "";
    P st;
    st.x = p1.px;
    st.y = p1.py;
    st.ans = "";
    queue<P> q;
    q.push(st);
    bool v[N][N];
    memset(v, false, sizeof(v));
    while (q.size()) {
        P now = q.front(), nex;
        q.pop();
        if (now.x == p1.x && now.y == p1.y) { //到达目标点
            tmp = now.ans;
            return true;
        }
        for (int i = 0; i < 4; i++) {
            nex = now;
            nex.x = now.x + dir[i][0];
            nex.y = now.y + dir[i][1];
            if (!pd(nex.x, nex.y)) continue;
            if (nex.x == p2.x && nex.y == p2.y) continue;   //不能经过箱子在的地方
            if (v[nex.x][nex.y]) continue;
            v[nex.x][nex.y] = true;
            nex.ans = now.ans + a[i];
            q.push(nex);
        }
    }
    return false;
}

string bfs1() {
    P st;
    st.x = st.y = st.px = st.py = -1;
    st.ans = "";
    for (int i = 0; i < r && (st.x == -1 || st.px == -1); i++) {
        for (int j = 0; j < c && (st.x == -1 || st.px == -1); j++) {
            if (s[i][j] == 'B') {    //箱子位置
                st.x = i;
                st.y = j;
                s[i][j] = '.';
            } else if (s[i][j] == 'S') {     //人的位置
                st.px = i;
                st.py = j;
                s[i][j] = '.';
            }
        }
    }

    queue<P> q;
    q.push(st);
    bool v[N][N][4];
    memset(v, false, sizeof(v));
    string ans = "Impossible.";
    ll cntans = INF, cnt = INF;
    while (q.size()) {
        P pre, now = q.front(), nex;
        q.pop();

        if (s[now.x][now.y] == 'T') {    //到达终点
            ll cntnow = 0;
            for (int i = 0; i < now.ans.length(); i++)
                if (now.ans[i] >= 'A' && now.ans[i] <= 'Z') ++cntnow;    //箱子移动距离
            if (cntnow < cntans || (cntnow == cntans && now.ans.length() < cnt)) {
                //箱子的移动距离小于之前的方案，或者箱子移动距离相同，但人移动距离小
                ans = now.ans;
                cntans = cntnow;
                cnt = now.ans.length();
            }
            continue;
        }
        for (int i = 0; i < 4; i++) {
            nex = now;
            nex.x = now.x + dir[i][0];
            nex.y = now.y + dir[i][1];
            if (!pd(nex.x, nex.y)) continue;  //出界判断
            if (v[nex.x][nex.y][i]) continue;    //访问判断

            pre = now;  //人应该在的位置
            if (i == 3) pre.y = now.y - 1;
            else if (i == 2) pre.y = now.y + 1;
            else if (i == 1) pre.x = now.x - 1;
            else pre.x = now.x + 1;

            if (!bfs2(pre, now)) continue;
            v[nex.x][nex.y][i] = true;
            nex.ans = now.ans + tmp;
            nex.ans = nex.ans + A[i];
            nex.px = now.x;
            nex.py = now.y;
            q.push(nex);
        }
    }
    return ans;
}

int main() {
    while (cin >> r >> c && r) {
        for (int i = 0; i < r; ++i) cin >> s[i];
        cout << "Maze #" << ++num << endl << bfs1() << endl << endl;
    }
    return 0;
}