一、學習目標

• 熟悉多源 BFS（多個起點同時擴散）與單源 BFS 的配合：先以多源 BFS 建出「危險/時間場」，再用單源 BFS 找可行最短路。
• 了解「BFS求最短步數、DFS/BFS 做區塊標記」如何在同題中混用（例如：先標不可越界/不可翻轉的區域，再在剩餘區域找步數或做轉換）。
• 對比權重圖最短路 = Dijkstra（小根堆 BFS）的思維，和無權圖 BFS 的差異。

二、觀念說明

多源 BFS（multi-source BFS）到底在幹嘛？

• 核心想法：把多個起點「同時」當作第 0 層，同步往外擴張。這樣得到的是「到最近起點的距離場」或「最早到達時間」。
• 建法：把所有源（例如所有怪物 M、所有腐爛橘子 2、所有邊界 O）一起入隊、距離 = 0。
• 正確性：BFS 天生就是分層；先擴張第 0 層，再第 1 層… 因此某格第一次被訪問的層數就是它距離最近源的最短步數（或最早時間）。
• 何時用：
  • 計算最短距離到最近的障礙/火/資源。
  • 計算某種影響（毒氣/腐爛/怪物）最早擴散到各格的時間。
• 口訣：「很多起點 → 一起丟 queue」。不用一個一個 BFS 再取最小，會慢也麻煩。

DFS 與 BFS 在同題中的分工

• 區塊標記（把一整塊連通的格子做標記、翻轉）：DFS/BFS 都可以。
  • 例如：Surrounded Regions 先從邊界 O 做 BFS/DFS 把能逃的 O 標成 E，再把剩下 O 翻成 X。
• 最短步數/最早時間：用 BFS（無權）。
• 混用範式：「先標記（DFS/BFS），後最短路（BFS）」 或反之，依賴題意。

無權圖 BFS vs. 0-1 BFS vs. Dijkstra

• 無權圖 BFS：每步代價相同（=1）；用 queue，第一次訪問即最短。
• 0-1 BFS：邊權只有 0 或 1；用 deque，權 0 的放前面、權 1 的放後面，O(n+m)。
• Dijkstra：非負權一般情況；用小根堆取當前最短距離節點做鬆弛（relax）。
  • 不變量：當你從堆中彈出 u 且該距離是最新的，dist[u] 已經是最短距離。
  • 常見坑：距離要 long long；可能會重複把同一點塞入堆（允許），出堆時用 if (d!=dist[u]) continue; 過濾陳舊狀態。

三、CSES實戰演練

題目1:Monsters

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

題意：
n×m 迷宮，有牆 #、空地 .、起點 A，以及多個怪物 M。每分鐘人與怪物都能向四鄰格移動。若人走到邊界格即可逃脫，但不能和怪物同時或更晚抵達同一格。判斷能否逃出，若可輸出最短路徑長與路徑字串。

解題思路:

• 第 1 階段：把所有 M 同時入隊做多源 BFS，得到 distM[x][y] = 怪物最早到達時間（無法到達設為很大）。
• 第 2 階段：從 A 單源 BFS，移動到 (nx,ny) 時需滿足 t+1 < distM[nx][ny]（人必須比怪物更早到）。一路記錄父方向，首度到達邊界即為最短逃生路。
• 起點若已在邊界，且 0 < distM[A]，可直接輸出長度 0（空路徑）。

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
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];

    vector<vector<int>> distM(n, vector<int>(m, (int)1e9));
    vector<vector<int>> distA(n, vector<int>(m, (int)1e9));
    vector<vector<char>> fromDir(n, vector<char>(m, 0));

    queue<pair<int,int>> qm, qa;
    pair<int,int> A(-1,-1);

    // 多源 BFS for monsters
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'M') {
                distM[i][j] = 0;
                qm.push(make_pair(i, j));
            } else if (g[i][j] == 'A') {
                A = make_pair(i, j);
            }
        }
    }

    while (!qm.empty()) {
        pair<int,int> cur = qm.front(); qm.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 (g[nx][ny] == '#') continue;
            if (distM[nx][ny] > distM[x][y] + 1) {
                distM[nx][ny] = distM[x][y] + 1;
                qm.push(make_pair(nx, ny));
            }
        }
    }

    // 人的 BFS
    qa.push(A);
    distA[A.first][A.second] = 0;

    // 若起點在邊界且安全
    if (A.first == 0 || A.first == n-1 || A.second == 0 || A.second == m-1) {
        if (0 < distM[A.first][A.second]) {
            cout << "YES\n0\n\n";
            return 0;
        }
    }

    pair<int,int> exitCell(-1,-1);
    while (!qa.empty()) {
        pair<int,int> cur = qa.front(); qa.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 (g[nx][ny] == '#') continue;
            int nt = distA[x][y] + 1;
            if (distA[nx][ny] != (int)1e9) continue;
            if (nt >= distM[nx][ny]) continue; // 不安全
            distA[nx][ny] = nt;
            fromDir[nx][ny] = dir[k]; // 走到 (nx,ny) 用了這個方向
            qa.push(make_pair(nx, ny));

            if (nx == 0 || nx == n-1 || ny == 0 || ny == m-1) {
                exitCell = make_pair(nx, ny);
                while (!qa.empty()) qa.pop(); // 提前結束
                break;
            }
        }
    }

    if (exitCell.first == -1) {
        cout << "NO\n";
        return 0;
    }

    // 回溯路徑：fromDir 記的是前進方向，往回走相反方向取父節點
    string path;
    int x = exitCell.first, y = exitCell.second;
    while (!(x == A.first && y == A.second)) {
        char c = fromDir[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; // 'R'
    }
    reverse(path.begin(), path.end());
    cout << "YES\n" << (int)path.size() << "\n" << path << "\n";
    return 0;
}

題目2:Shortest Routes I

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

題意：
給 n 節點、m 條非負權重有向邊，輸出從 1 到每個節點的最短距離。若不可達，常以極大值（例如 1e18）表示。

解題思路:

• 標準 Dijkstra：dist[1]=0，用小根堆 priority_queue<pair<long long,int>,...> 每次取當前最小距離節點做鬆弛。
• 用 long long 存距離；INF 可設 1e18。

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

struct Edge { int to; long long w; };

int main() {
    int n, m; 
    cin >> n >> m;
    vector<vector<Edge> > g(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b; long long w;
        cin >> a >> b >> w;
        g[a].push_back(Edge{b, w});
    }

    const long long INF = (long long)1e18;
    vector<long long> dist(n + 1, INF);
    vector<char> vis(n + 1, 0);
    dist[1] = 0;

    typedef pair<long long,int> Node; // (dist, id)
    priority_queue<Node, vector<Node>, greater<Node> > pq;
    pq.push(Node(0, 1));

    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        long long d = cur.first;
        int u = cur.second;
        if (vis[u]) continue;
        vis[u] = 1;
        if (d != dist[u]) continue;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].to;
            long long nd = d + g[u][i].w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push(Node(nd, v));
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << dist[i];
    }
    cout << '\n';
    return 0;
}

四、Leetcode實戰演練

題目1:Rotting Oranges

原題:
https://leetcode.com/problems/rotting-oranges/description/

題意:
0=空、1=新鮮橘子、2=腐爛橘子。每分鐘腐爛會傳給四鄰的新鮮橘子。求使所有新鮮橘子腐爛的最少分鐘數；若不可能，回傳 -1。

解題思路:
先把所有 2 同時入隊做多源 BFS；每層代表 1 分鐘。
紀錄新鮮橘子總數 fresh，BFS 過程中每次腐爛一顆就遞減；最後若 fresh > 0 則 -1，否則回傳最後時間。

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int n = (int)grid.size();
        if (n == 0) return 0;
        int m = (int)grid[0].size();

        const int DX[4] = {-1, 1, 0, 0};
        const int DY[4] = {0, 0, -1, 1};

        queue<pair<int,int> > q;
        int fresh = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) q.push(make_pair(i, j));
                else if (grid[i][j] == 1) ++fresh;
            }

        if (fresh == 0) return 0;

        int minutes = -1;
        while (!q.empty()) {
            int qs = (int)q.size();
            minutes++;
            while (qs--) {
                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 (grid[nx][ny] != 1) continue;
                    grid[nx][ny] = 2;
                    fresh--;
                    q.push(make_pair(nx, ny));
                }
            }
        }
        return (fresh == 0) ? max(0, minutes) : -1;
    }
};

題目2:Surrounded Regions

原題:
https://leetcode.com/problems/surrounded-regions/description/

題意：
給 X/O 棋盤，上下左右連通的一群 O 若沒有接觸到邊界，就把那群 O 全翻成 X；否則保留。回傳最終棋盤。

解題思路（BFS 寫法；DFS 亦可）:

• 從邊界上的 O 出發做 BFS/DFS，把所有與邊界連通的 O 標記為「能逃出」的 E。
• 掃整板：把剩下沒標的 O → X；再把 E 還原為 O。
• 這是典型「先標不可翻/保留的區塊，再統一處理其餘區塊」的 DFS/BFS 應用。

class Solution {
    // 將邊界上的 'O' 入隊並標成 'E'
    void push_if_O(vector<vector<char>>& board, int n, int m,
                   int x, int y, queue<pair<int,int>>& q) {
        if (x >= 0 && x < n && y >= 0 && y < m && board[x][y] == 'O') {
            board[x][y] = 'E';
            q.push(make_pair(x, y));
        }
    }
public:
    void solve(vector<vector<char>>& board) {
        int n = (int)board.size();
        if (n == 0) return;
        int m = (int)board[0].size();

        queue<pair<int,int>> q;

        // 1) 從「邊界的 O」開始做 BFS（先標成 E，代表能逃出去）
        for (int i = 0; i < n; ++i) {
            push_if_O(board, n, m, i, 0, q);
            push_if_O(board, n, m, i, m - 1, q);
        }
        for (int j = 0; j < m; ++j) {
            push_if_O(board, n, m, 0, j, q);
            push_if_O(board, n, m, n - 1, j, q);
        }

        // 2) 從這些 E 擴張，把所有與邊界連通的 O 標為 E
        const int DX[4] = {-1, 1, 0, 0};
        const int DY[4] = {0, 0, -1, 1};

        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 && board[nx][ny] == 'O') {
                    board[nx][ny] = 'E';
                    q.push(make_pair(nx, ny));
                }
            }
        }

        // 3) 統一翻轉：剩下的 O（被包圍）→ X；E（能逃）→ O
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == 'E') board[i][j] = 'O';
            }
    }
};