一、學習目標

• 了解 BFS（Breadth-First Search） 在無權圖求最短邊數路徑的原理與不變量。
• 熟悉四種常見套路：網格 BFS、一般圖 BFS（路徑重建）、多源 BFS、狀態圖 BFS。
• 釐清實作細節：何時標記 visited（入隊即標）、如何記錄父節點以重建路徑、如何處理障礙/禁區。

二、觀念說明

BFS 是什麼？什麼時候用？

• 定義：在圖（graph）上用**佇列（queue）**做分層擴張的搜尋。從起點出發，先處理距離 1 的點、再距離 2 的點……一層一層擴散。
• 適用情境：邊等權（每條邊代價一樣）或你在意的是最少步數/最少邊數。例：迷宮最短步數、社交網路最少轉介數、無權圖的最短路徑。
• 不適用：邊有不同權重（用 Dijkstra / 0-1 BFS / SPFA / Bellman-Ford）、或需要全排列/回溯式完整枚舉（DFS/回溯較合適）。

為什麼 BFS 保證最短？

• 層（level）觀點：把距離起點為 k 的所有點視為第 k 層。BFS 每次都先把第 k 層完整擴張，才會碰到第 k+1 層。因此第一次被訪問到的點，其距離就是最短路徑長度。
• 不變量：
  • 佇列中的節點，其 dist 非遞減（先入隊的距離不大於後入隊）。
  • 當一個節點第一次被彈出時，圖上不可能存在更短的路徑沒被發現（否則它早該在更前面的層被入隊）。
• 常見等價說法：BFS ≈ 在每條邊權重都等於 1 的圖上套 Dijkstra。

訪問與標記：為什麼「入隊就標記」？

• 原則：一個節點入隊當下就把 visited 設為已訪，避免同層被重複入隊（否則同一層的多個父節點會把它塞多次，時間記憶體爆炸）。
• 替代做法（不推薦）：出隊才標記。會導致同一節點在同層被加入多次，退化為大常數甚至 TLE。

距離與路徑重建（path reconstruction）

距離：可維護 dist[u] = dist[parent[u]] + 1 ，或在網格用 dist[x][y]。

路徑：對每個新訪點 v 記 parent[v] = u（或在網格記「我是從哪個方向來的」），到達終點後從終點往回追到起點再反轉，即最短路徑。

四種常見 BFS 模式

A. 網格 BFS（grid BFS）

節點是格子 (x,y)，鄰居是四/八方向。
邊界檢查、障礙判斷、入隊即標，可記方向字元 U/D/L/R 來回溯路徑。
複雜度：O(nm)。

B. 一般圖 BFS（adj list）

用鄰接串列 vector<vector> g;。
優先級：讀入 → 建圖 → BFS → 回溯路徑/輸出距離。
複雜度：O(n + m)。

C. 多源 BFS（multi-source）

一次把多個起點都丟進佇列、dist=0，等價把它們視為同一層起點。
常用於「距離最近的…」或擴散模型（火勢、毒氣）：先擴張障礙/火，再跑人員 BFS 等。

D. 狀態圖 BFS（state-space BFS）

節點不一定是單純的位置，可能是位置 + 狀態（鑰匙集合、剩餘步數、方向…）。
例：迷宮拿鑰匙開門 → 狀態可設 (x, y, mask)，mask是鑰匙位元集合。
警告：狀態爆炸（N * 狀態數）。要先估上界與可行性。

常見陷阱

• 重複入隊：沒有「入隊即標」，導致一點被進佇列很多次 → TLE。
• 忘記清初值：多組測資時 visited/dist/parent 未重設。
• 網格回溯方向寫反：建議同時準備前進與反向對應表。
• 狀態 BFS 忘了把狀態放進 visited key：只標記 (x,y) 而忽略 mask，會把不同狀態錯誤視為已訪或未訪。
• 圖太大用鄰接矩陣：O(n^2) 記憶體炸；應改用鄰接串列。
• 提前返回時沒建好 parent：如果要輸出路徑，請在「第一次到終點」再回溯（或保證 parent 齊全）。

複雜度

時間：O(V + E)，網格是 O(nm)。
空間：O(V)（含 visited、dist、parent/方向）。

三、CSES實戰演練

題目1 : Labyrinth

原題:
https://cses.fi/problemset/task/1193

題意:
給 n x m 地圖，牆 #、空地 .，起點 A、終點 B。問是否可達，若可，輸出最短路徑長度與路徑（UDLR）。

解題思路:

• 從 A 做 BFS，四方向擴張，牆不可走。
• 以 parentDir[x][y] 記錄該格是從哪個方向走來（例如走到 (nx,ny) 時記 'U'/'D'/'L'/'R' 表示回溯方向），終點到達後回溯重建字串。

#include <bits/stdc++.h>
using namespace std;

static const int dx[4] = {-1, 1, 0, 0};
static const int dy[4] = {0, 0, -1, 1};
static const char dir[4] = {'U','D','L','R'}; // 從父到子「前進方向」

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; ++i) cin >> g[i];

    pair<int,int> A(-1,-1), B(-1,-1);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == 'A') A = make_pair(i,j);
            if (g[i][j] == 'B') B = make_pair(i,j);
        }

    vector<vector<int> > vis(n, vector<int>(m, 0));
    vector<vector<char> > parentDir(n, vector<char>(m, 0)); // 記錄「走到這格時用的前進方向」
    queue<pair<int,int> > q;

    q.push(A);
    vis[A.first][A.second] = 1;

    while (!q.empty()) {
        pair<int,int> cur = q.front(); q.pop();
        int x = cur.first, y = cur.second;
        if (x == B.first && y == B.second) break;

        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (vis[nx][ny]) continue;
            if (g[nx][ny] == '#') continue;
            vis[nx][ny] = 1;
            parentDir[nx][ny] = dir[k]; // 從 (x,y) 走到 (nx,ny) 的前進方向
            q.push(make_pair(nx, ny));
        }
    }

    if (!vis[B.first][B.second]) {
        cout << "NO\n";
        return 0;
    }

    // 從 B 回溯到 A：讀的是「前進方向」，所以移動要走相反；最後再 reverse 得到正向路徑
    string path;
    int x = B.first, y = B.second;
    while (x != A.first || y != A.second) {
        char c = parentDir[x][y];
        path.push_back(c);          // 記住「前進方向」字元
        // 走回父節點（相反方向）
        if (c == 'U') x += 1;
        else if (c == 'D') x -= 1;
        else if (c == 'L') y += 1;
        else  y -= 1;
    }
    reverse(path.begin(), path.end()); // 變成從 A 到 B 的正向指令

    cout << "YES\n";
    cout << (int)path.size() << "\n";
    cout << path << "\n";
    return 0;
}

題目2 : Message Route

原題:
https://cses.fi/problemset/task/1667

題意：
n 個節點、m 條邊（無向、無權），從 1 到 n 的最短路徑；不可達輸出 IMPOSSIBLE。

解題思路:
標準圖 BFS，parent[v] 記錄前驅；到 n 後回溯得到路徑。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n+1);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> vis(n+1, 0), parent(n+1, -1);
    queue<int> q;
    q.push(1); vis[1] = 1;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u==n) break;
        for (int v : g[u]) if (!vis[v]) {
            vis[v] = 1;
            parent[v] = u;
            q.push(v);
        }
    }

    if (!vis[n]) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    vector<int> path;
    for (int v=n; v!=-1; v=parent[v]) path.push_back(v);
    reverse(path.begin(), path.end());

    cout << (int)path.size() << "\n";
    for (int i=0; i<(int)path.size(); i++) {
        if (i) cout << ' ';
        cout << path[i];
    }
    cout << "\n";
    return 0;
}

四、Leetcode實戰演練

題目1 : Flood Fill

原題:
https://leetcode.com/problems/flood-fill/description/

題意：
把影像 image 由起點 (sr, sc) 開始，把連通且顏色等於起點原色的所有格子，統一改成 newColor（4 向相鄰）。

解題思路（BFS）:
先記下起點原色 orig，若 orig == newColor 直接回傳（避免死循環）。
佇列裝座標；入隊即塗色（等同 visited），再擴張上下左右四鄰。

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int n = (int)image.size(), m = (int)image[0].size();
        int orig = image[sr][sc];
        if (orig == newColor) return image;

        static const int dx[4] = {-1, 1, 0, 0};
        static const int dy[4] = {0, 0, -1, 1};

        queue<pair<int,int>> q;
        q.push(make_pair(sr, sc));
        image[sr][sc] = newColor; // 入隊即標記：直接上色

        while (!q.empty()) {
            pair<int,int> cur = q.front(); q.pop();
            int x = cur.first, y = cur.second;
            for (int k = 0; k < 4; ++k) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (image[nx][ny] != orig) continue;
                image[nx][ny] = newColor;        // 入隊即標記
                q.push(make_pair(nx, ny));
            }
        }
        return image;
    }
};

題目2 : Maximum Depth of Binary Tree

原題:
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/?envType=problem-list-v2&envId=breadth-first-search

題意:
給定一棵二元樹的根節點 root，請回傳樹的最大深度（從根到最遠葉節點的最長路徑所經過的節點數）。空樹深度為 0。

解題思路:
一層一層掃描。BFS 的 queue 內恰好維持「目前這一層」的所有節點；每處理完一層，深度 +1。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;

        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;

        while (!q.empty()) {
            int sz = (int)q.size();   // 這一層有幾個節點
            while (sz--) {
                TreeNode* node = q.front(); q.pop();
                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }
            depth++; // 這一層處理完了
        }
        return depth;
    }
};