您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 1254 推箱子：雙重 BFS 經典解法完整代碼

編輯：關於C++

題目大意

同 3122：M×N 房間（≤7×7），推箱子到目標位置，求最少推動次數。輸入多測試用例。

算法：BFS 嵌套 BFS

外層 BFS：箱子狀態（位置 + 人位置 + 推動步數）
內層 BFS：判斷人能否從當前位置走到箱子後方推動位置
狀態標記：vis[box_x][box_y][dir] 箱子在某位置向某方向是否推過

完整可編譯代碼


#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 11;
int mat[MAXN][MAXN];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
bool vis[MAXN][MAXN][4], vm[MAXN][MAXN];
int man_x, man_y, box_x, box_y, en_x, en_y;
int n, m;

struct Pos { int x, y; };
struct Node { int step; Pos box, man; };

// 內層 BFS：人能否到達 (target_x, target_y)
bool canReach(int target_x, int target_y, int man_x, int man_y, int box_x, int box_y) {
    memset(vm, 0, sizeof(vm));
    queue q;
    q.push({man_x, man_y});
    vm[man_x][man_y] = true;
    vm[box_x][box_y] = true; // 箱子位置視為牆

    while (!q.empty()) {
        Pos cur = q.front(); q.pop();
        if (cur.x == target_x && cur.y == target_y) return true;
        for (int i = 0; i < 4; i++) {
            Pos nxt = {cur.x + dir[i][0], cur.y + dir[i][1]};
            if (nxt.x < 1 || nxt.x > n || nxt.y < 1 || nxt.y > m) continue;
            if (mat[nxt.x][nxt.y] != 0) continue; // 牆或邊界
            if (!vm[nxt.x][nxt.y]) {
                vm[nxt.x][nxt.y] = true;
                q.push(nxt);
            }
        }
    }
    return false;
}

// 外層 BFS：箱子移動
void bfs() {
    queue q;
    Node start = {0, {box_x, box_y}, {man_x, man_y}};
    q.push(start);
    memset(vis, 0, sizeof(vis));

    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.box.x == en_x && cur.box.y == en_y) {
            cout << cur.step << endl;
            return;
        }
        for (int i = 0; i < 4; i++) {
            Pos nxtBox = {cur.box.x + dir[i][0], cur.box.y + dir[i][1]};
            Pos nxtMan = {cur.box.x, cur.box.y}; // 推箱後人站在箱子原位置
            // 目標位置：箱子反方向相鄰格
            Pos targetMan = {cur.box.x - dir[i][0], cur.box.y - dir[i][1]};

            // 邊界/牆壁檢查
            if (nxtBox.x < 1 || nxtBox.x > n || nxtBox.y < 1 || nxtBox.y > m) continue;
            if (mat[nxtBox.x][nxtBox.y] != 0) continue;
            if (targetMan.x < 1 || targetMan.x > n || targetMan.y < 1 || targetMan.y > m) continue;
            if (mat[targetMan.x][targetMan.y] != 0) continue;

            // 狀態去重
            if (vis[cur.box.x][cur.box.y][i]) continue;
            // 人可達性檢查
            if (!canReach(targetMan.x, targetMan.y, cur.man.x, cur.man.y, cur.box.x, cur.box.y)) continue;

            vis[cur.box.x][cur.box.y][i] = true;
            q.push({cur.step + 1, nxtBox, nxtMan});
        }
    }
    cout << -1 << endl;
}

int main() {
    int T; cin >> T;
    while (T--) {
        memset(mat, -1, sizeof(mat)); // 邊界初始化為 -1（牆）
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> mat[i][j];
                if (mat[i][j] == 2) { box_x = i; box_y = j; mat[i][j] = 0; }
                else if (mat[i][j] == 3) { en_x = i; en_y = j; mat[i][j] = 0; }
                else if (mat[i][j] == 4) { man_x = i; man_y = j; mat[i][j] = 0; }
            }
        }
        bfs();
    }
    return 0;
}