題目背景

經典推箱子遊戲簡化版：M×N 房間（2≤M,N≤7），有牆壁（1）、箱子（2）、目標（3）、搬運工（4）、空地（0）。搬運工只能推箱子不能拉。箱子推入死角則無法移動，推靠牆只能沿牆移動。求最少推動格數，不可達輸出 -1。

算法核心：雙層 BFS

• 外層 BFS：搜索箱子狀態（位置），每步代價為 1 次推動
• 內層 BFS：判斷搬運工能否走到箱子後方進行推動（不計步數）
• 狀態標記：vis[box_x][box_y][dir] 記錄箱子在某位置向某方向是否已推過

關鍵細節

1. 箱子移動前，必須驗證人能到達推箱位置（箱子反方向相鄰格）
2. 人員移動忽略箱子當前位置（視為牆），但可走其他空地
3. 目標狀態：箱子到達目標位置，無論人員位置
4. 地圖小（≤7×7），狀態空間極小，BFS 足夠

代碼框架（C++）

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;

int Map[8][8];
bool vis[8][8][4], us[8][8]; // 箱子推過方向、人走過點
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

struct Node {
    int x, y;     // 箱子坐標
    int xx, yy;   // 人坐標
    int t;        // 推動次數
} st, ed;

struct Pos { int x, y; } a, b;

int n, m;
queue<Node> q;

void Bfs() {
    // 外層 BFS：箱子狀態
    // 內層 BFS：人能否到達推箱位置
    // 詳見完整代碼...
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> n >> m;
        memset(Map, 0, sizeof(Map));
        // 讀入地圖，記錄箱子、人、目標初始位置
        // 初始化 vis、調用 Bfs()
    }
    return 0;
}

優化提示

• 使用三維數組 vis[8][8][4] 標記箱子在 (x,y) 向方向 d 推過
• 內層 BFS 每次重置 us 數組（人走過標記）
• 箱子推到目標時直接返回步數，保證最優