推箱子

題目描述

你（You）正在玩一款叫做“推箱子”的游戲，任務是避開巖石（Rock）并且將箱子（Box）推到目標位置（Target），箱子非常沉，而且你每次只能移動一步，所以希望推箱子的次數越少越好，如果有多個方法，那么讓總得移動的次數盡量少，如果還有多個方法，那么任意一個都行，你可以寫一個程式來找出一條最優的路線嗎？

Input

輸入包含若干局游戲，每一局第一行包含兩個整數 r,c(1 \leq r,c \leq 20)r,c(1≤r,c≤20)，下面 r 行每行包含 c 個字符，巖石用’#‘表示，空地用’.'表示，你開始的位置用’S’表示，箱子起始位置用’B’表示，目標位置用’T’表示，輸入以 0 0 結束，

Output

如果無法完成游戲，輸出"Impossible."，否則輸出一條最優路線，路線中的每一步用 ‘N’ ‘S’ ‘E’ ‘W’ ‘n’ ‘s’ ‘e’ ‘w’ 其中的一個字母表示，大寫字母代表推著箱子移動了一步，小寫代表只是移動了一步，每兩局游戲之間輸出一個空行，本題答案不唯一，符合要求的答案均正確

Sample Input

1 7
SB…T
1 7
SB…#.T
7 11
###########
#T##…#
#.#.#…####
#…B…#
#.######…#
#…S…#
###########
8 4
…
.##.
.#…
.#…
.#.B
.##S
…
###T
0 0

Sample Output

Maze #1
EEEEE

Maze #2
Impossible.

Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN

Maze #4
swwwnnnnnneeesssSSS

解題思路

這一題看上去好像很難，其實只是比較簡單的bfs，一定要相信自己的實力是可以寫出來的，不能有畏難情緒，這里先對箱子進行bfs找終點，對于箱子走的每一步，都需要對人進行bfs來確定箱子是否可以走這一步，因為我們要記錄人和箱子走的路線，所以可以建立兩個陣列來一一對應每一步的方向，走完后放入保存答案的 string 字串（選擇用 string 而不用 char 的原因是因為，每次走一步，直接把已經走過的方向加上當前步的方向即可，較為簡單），

注意事項

1.在對人bfs的時候，還需要傳入當前箱子的位置，因為人不能穿過箱子，
2.人和箱子的bfs中使用的 vis 陣列是兩個，不能混淆，
3.輸出結果的時候，每組資料之間有空行，所以需要兩個換行，

代碼實作

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

using namespace std;

char maze[25][25];
int sx, sy, bx, by;
int r, c;

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
char BOX[4] = { 'E', 'S', 'W', 'N' };
char MAN[4] = { 'e', 's', 'w', 'n' };

string ans;//保存答案

struct person {
    int x;
    int y;
    string path;
};//保存人每一步的位置和路徑

struct box {
    int px;
    int py;
    int bx;
    int by;
    string path;
};//保存箱子每一步的位置和路以及當前人的位置

bool check(int x, int y)
{
    return x >= 0 && y >= 0 && x < r && y < c && maze[x][y] != '#';
}

//對人進行bfs，需要當前人和箱子的位置，以及人需要去的位置，路徑用path保存后回傳
bool bfs_person(int bbx, int bby, int ppx, int ppy, int eex, int eey, string &path)
{
    int vis[25][25];
    memset(vis, 0, sizeof(vis));
    queue<person> quep;
    vis[bbx][bby] = 1;
    vis[ppx][ppy] = 1;
    quep.push(person{ ppx, ppy, "" });
    while (quep.size())
    {
        person pnow = quep.front();
        quep.pop();
        if (pnow.x == eex && pnow.y == eey)
        {
            path = pnow.path;
            return true;
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = pnow.x + dx[i];
            int ny = pnow.y + dy[i];
            if (check(nx, ny) && vis[nx][ny] == 0)
            {
                vis[nx][ny] = 1;
                person next;
                next.x = nx;
                next.y = ny;
                next.path = pnow.path + MAN[i];
                quep.push(next);
            }
        }
    }
    return false;
}

bool bfs_box()
{
    int vis[25][25];
    memset(vis, 0, sizeof(vis));
    vis[bx][by] = 1;
    queue<box> queb;
    queb.push({ sx, sy, bx, by, "" });
    while (queb.size())
    {
        box bnow = queb.front();
        queb.pop();
        if (maze[bbx][bby] == 'T')//直接判斷是不是到達了終點，所以可以不需要終點坐標
        {
             ans = next.path;
             return true;
        }
        for (int i = 0; i < 4; i++)
        {
            int bbx = bnow.bx + dx[i];
            int bby = bnow.by + dy[i];
            int ppx = bnow.bx - dx[i];//人在箱子后，即為減
            int ppy = bnow.by - dy[i];
            string path = "";
            if (check(bbx, bby) && check(ppx, ppy) && vis[bbx][bby] == 0)
            {
                if (bfs_person(bnow.bx, bnow.by, bnow.px, bnow.py, ppx, ppy, path))判斷人可不可以到達箱子后，推動箱子走這一步
                {
                    vis[bbx][bby] = 1;
                    box next;
                    next.bx = bbx;
                    next.by = bby;
                    next.px = bnow.bx;//人的位置應該是當前箱子的位置，因為推動箱子走了一步
                    next.py = bnow.by;
                    next.path = bnow.path + path + BOX[i];
                    queb.push(next);
                }
            }
        }
    }
    return false;
}

int main()
{
    int cnt = 0;//用一個變數來記錄當前是第幾個樣例
    while(~scanf("%d%d", &r, &c))
    {
        if (r == 0 && c == 0)
            break;
        cnt++;
        memset(maze, '\0', sizeof(maze));
        for (int i = 0; i < r; i++)
        {
            for (int j = 0; j < c; j++)
            {
                cin >> maze[i][j];
                if (maze[i][j] == 'B')
                    bx = i, by = j;//初始箱子的坐標
                if (maze[i][j] == 'S')
                    sx = i, sy = j;//初始人的坐標
            }
        }
        cout << "Maze #" << cnt << endl;
        if (bfs_box())
            cout << ans << endl << endl;
        else
            cout << "Impossible." << endl << endl;
    }
	return 0;
}