HDU 5335 Walk Out：BFS 求字典序最小的最短路徑

問題描述

給定 n × m 的 0/1 矩陣地圖，從 (1,1) 走到 (n,m)，只能上下左右移動。路徑上的數字組成二進制串（忽略前導 0），求字典序最小的路徑對應的二進制序列。

核心觀察

1. 最短路長度固定：任何從左上到右下的路徑長度均為 n + m - 1
2. 字典序最小策略：優先走 0，只在無 0 可走時選 1
3. 連通塊預處理：若起點為 0，先 BFS 找出所有與起點相連的 0 區域，作為擴展起點集

分層 BFS 算法流程

// 核心邏輯：按層擴展，每層優先收集值為 0 的鄰居
vector<pair<short,short>> q_cur, q_next_0, q_next_1;
q_cur.push_back({1,1});
vis2[1][1] = true;
path[1] = G[1][1]; // 起點值

for (int step = 2; step <= n+m-1; ++step) {
    q_next_0.clear(); q_next_1.clear();
    for (auto [x,y] : q_cur) {
        for (int dir = 2; dir < 4; ++dir) { // 只向右、向下（避免回頭）
            int nx = x + dx[dir], ny = y + dy[dir];
            if (invalid(nx,ny) || vis2[nx][ny]) continue;
            vis2[nx][ny] = true;
            if (G[nx][ny] == 0) q_next_0.emplace_back(nx,ny);
            else q_next_1.emplace_back(nx,ny);
        }
    }
    if (!q_next_0.empty()) {
        path[step] = 0;
        q_cur = move(q_next_0);
    } else {
        path[step] = 1;
        q_cur = move(q_next_1);
    }
}

關鍵優化點

• 入隊即標記訪問：防止重複入隊導致 MLE（原作者比賽時因出隊才標記導致爆內存）
• 方向剪枝：只考慮右、下兩個方向，因為最短路不需回頭
• 雙隊列交替：當前層節點 q_cur，下一層 0/1 分離存儲

完整代碼框架

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
bool G[MAXN][MAXN], vis[MAXN][MAXN], vis2[MAXN][MAXN];
int dx[4] = {-1,0,1,0}, dy[4] = {0,-1,0,1};
int path[2005];

int main() {
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        // 讀入地圖...
        // 1. 起點為 0 時，BFS 擴展連通塊
        // 2. 確定起始點集合 qq
        // 3. 分層 BFS 構建 path[]
        // 4. 輸出 path[1..len]
    }
}

複雜度分析

• 時間：O(n·m)，每個格子最多入隊一次
• 空間：O(n·m)，訪問標記數組與隊列存儲