HDU Swipe Bo：BFS + 狀態壓縮解迷宮謎題

題目背景

「Swipe Bo」是一款益智遊戲，主角是一個方形的藍色豆腐 Bo。玩家可以向上/下/左/右滑動，Bo 會沿直線移動直到撞牆。目標是用最少步數將 Bo 移動到出口。地圖包含牆壁 (#)、起點 (S)、出口 (E)、空地 (.)、鑰匙 (K，最多 7 把)、轉向標誌 (L, U, D, R)。出口若被鎖住，必須先收集所有鑰匙才能解鎖。轉向格會強制 Bo 改變方向，不計步數。地圖大小 ≤ 200×200，測試案例 ≤ 40。

解題思路

這是一個帶狀態的最短路問題，適合用 BFS + 狀態壓縮：

• 狀態定義：(x, y, keys_mask)，其中 keys_mask 用 7 位二進制表示已收集的鑰匙集合。
• 移動規則：從當前位置向四個方向滑動，直到撞牆或遇到轉向格。轉向格會強制改變方向繼續滑動，不增加步數。每次滑動（包括初始方向選擇）算作一步。
• BFS 搜索：從起點開始，嘗試四個初始方向。使用訪問數組 vis[x][y][mask] 避免重複。當到達出口且已收集所有鑰匙（或無鑰匙）時返回步數。
• 終止條件：若隊列耗盡仍未到達出口，輸出 -1。

關鍵代碼片段

struct Node { int x, y, sta, stp; };
int dir[4][2] = {{0,-1},{0,1},{-1,0},{1,0}}; // L,R,U,D
bool vis[205][205][1<<7];
int n, m, k;
char map[205][205];
int keyId[205][205];

// 判斷移動是否合法並處理轉向
bool judge(Node &now, int &d) {
    if (now.x < 0 || now.x >= n || now.y < 0 || now.y >= m) return false;
    if (map[now.x][now.y] == '#') return false;
    char c = map[now.x][now.y];
    if (c == 'L') d = 0;
    else if (c == 'R') d = 1;
    else if (c == 'U') d = 2;
    else if (c == 'D') d = 3;
    else if (c == 'K') now.sta |= (1 << keyId[now.x][now.y]);
    return true;
}

// BFS 主循環
int bfs() {
    queue q;
    Node start = {sx, sy, 0, 0};
    vis[sx][sy][0] = true;
    q.push(start);
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.x == ex && cur.y == ey && cur.sta == (1<

注意事項

轉向格不計步數，但會改變滑動方向。
鑰匙數量 ≤ 7，狀態壓縮可行（128 種狀態）。
出口若被鎖，視為不可通行，直到收集齊所有鑰匙。
輸入測試案例以四個 0 結束。