题目分析

题目要求在一个迷宫中，将箱子(B)从起点推到目标位置(T)。玩家(S)需要绕过障碍物(#)来推动箱子。每次推动箱子时，玩家必须站在箱子移动方向的相反位置。需要找到推动箱子的最短路径，如果无法完成则输出"Impossible."。

解题思路

1. 双BFS搜索：
   • 使用两个BFS：一个用于计算玩家到达特定位置的最短路径（pbfs），另一个用于计算箱子移动的最短路径（bbfs）。
2. 状态记录：
   • 记录箱子的位置和朝向（4个方向）。
   • 记录玩家到达推动位置的最短路径。
3. 路径重建：
   • 当箱子到达目标位置时，回溯推动路径和玩家移动路径，生成完整解决方案。

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <unordered_map>
using namespace std;

struct State {
    int bx, by;    // 箱子位置
    int px, py;    // 玩家位置
    string path;   // 路径记录
    int pushes;     // 推动次数
    int moves;      // 总移动次数
    
    bool operator<(const State& other) const {
        if (pushes != other.pushes) return pushes > other.pushes;
        return moves > other.moves;
    }
};

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const char dir[] = {'N', 'S', 'W', 'E'};
const char walk_dir[] = {'n', 's', 'w', 'e'};

string solve_maze(vector<string>& maze, int r, int c, int sx, int sy, int bx, int by, int tx, int ty) {
    priority_queue<State> pq;
    unordered_map<string, bool> visited;
    
    pq.push({bx, by, sx, sy, "", 0, 0});
    string key = to_string(bx) + "," + to_string(by) + "," + to_string(sx) + "," + to_string(sy);
    visited[key] = true;
    
    while (!pq.empty()) {
        State curr = pq.top();
        pq.pop();
        
        if (curr.bx == tx && curr.by == ty) {
            return curr.path;
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = curr.px + dx[i];
            int ny = curr.py + dy[i];
            
            if (nx < 0 || nx >= r || ny < 0 || ny >= c || maze[nx][ny] == '#') {
                continue;
            }
            
            string new_path = curr.path;
            int new_pushes = curr.pushes;
            int new_moves = curr.moves + 1;
            
            if (nx == curr.bx && ny == curr.by) {  // 推动箱子
                int nbx = curr.bx + dx[i];
                int nby = curr.by + dy[i];
                
                if (nbx < 0 || nbx >= r || nby < 0 || nby >= c || maze[nbx][nby] == '#') {
                    continue;
                }
                
                new_path += dir[i];
                new_pushes++;
                string new_key = to_string(nbx) + "," + to_string(nby) + "," + to_string(nx) + "," + to_string(ny);
                if (!visited[new_key]) {
                    visited[new_key] = true;
                    pq.push({nbx, nby, nx, ny, new_path, new_pushes, new_moves});
                }
            } else {  // 只是移动
                new_path += walk_dir[i];
                string new_key = to_string(curr.bx) + "," + to_string(curr.by) + "," + to_string(nx) + "," + to_string(ny);
                if (!visited[new_key]) {
                    visited[new_key] = true;
                    pq.push({curr.bx, curr.by, nx, ny, new_path, curr.pushes, new_moves});
                }
            }
        }
    }
    
    return "Impossible.";
}

int main() {
    int r, c, maze_num = 1;
    while (cin >> r >> c, r || c) {
        vector<string> maze(r);
        int sx, sy, bx, by, tx, ty;
        
        for (int i = 0; i < r; i++) {
            cin >> maze[i];
            for (int j = 0; j < c; j++) {
                if (maze[i][j] == 'S') {
                    sx = i; sy = j;
                    maze[i][j] = '.';
                } else if (maze[i][j] == 'B') {
                    bx = i; by = j;
                    maze[i][j] = '.';
                } else if (maze[i][j] == 'T') {
                    tx = i; ty = j;
                    maze[i][j] = '.';
                }
            }
        }
        
        cout << "Maze #" << maze_num << endl;
        string result = solve_maze(maze, r, c, sx, sy, bx, by, tx, ty);
        cout << result << endl << endl;
        maze_num++;
    }
    return 0;
}