【C++】競程筆記（BFS：廣度優先搜尋）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

流水問題

以 NTUCPC Guide 舉的例子來說的話，水流只能往上下左右流，而且是同時流，然後求每個空地格子幾秒後會有水。

具體做法是先將流水的起點定為 0 秒，之後向上下左右擴散一單位的水並 + 1 秒，注意這邊要做邊界檢查，如下圖的第三張。

Image Source：https://guide.ntucpc.org/AlgorithmTechnique/bfs/

而在程式設計上，右上角那塊 2 是最容易犯錯的，因為我們都想說上下左右 + 1，第一次寫的時候會沒想到那塊 2 左邊跟下方都有一塊 1，最後加起來還可能會是 3，就比較不合理，這也是要在程式設計上要注意的地方。

以下是有關這個流水問題的範例程式碼（From : NTUCPC Guide | BFS）：

// from NTUCPC Guide
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1000;
string board[MAXN + 2];
int ans[MAXN + 2][MAXN + 2];
using pii = pair<int, int>;
pii dir[4] = {pii(-1, 0), pii(1, 0), pii(0, -1), pii(0, 1)};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, si, sj; // 起點是 (si, sj)
    cin >> n >> m >> si >> sj;
    for (int i = 1; i <= n; i++) {
        cin >> board[i];
        board[i] = '#' + board[i] + '#';
    }
    board[0] = board[n + 1] = string(m + 2, '#');
 
    for (int i = 1; i <= n; i++)
        fill(ans[i] + 1, ans[i] + m + 1, -1);
    // ans[i][j] = -1 代表 (i, j) 目前沒有水
 
    ans[si][sj] = 0;
    // 剛剛新流到水的格子
    vector<pii> last = {pii(si, sj)};
    // last 裡面的格子是答案為 t 的格子
    for (int t = 0; t <= n * m; t++) {
        // 流出去的格子，答案是 t + 1
        vector<pii> nxt;
        for (auto [x, y] : last) {
            for (auto [dx, dy] : dir) {
                int nx = x + dx, ny = y + dy;
                if (board[nx][ny] == '#' || ans[nx][ny] != -1) continue;
                ans[nx][ny] = t + 1;
                nxt.emplace_back(pii(nx, ny));
            }
        }
        last = nxt;
    }
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cout << ans[i][j] << " \n"[j == m];
    // 輸出 -1 代表水流不到
}

這個流水問題有限制 $N, M \leq 1000$ ，所以可設個變數 int MAXN = 1000，或是不設直接寫數字也可以。

然後就可以開個 MAXN + 2 的陣列（+ 2 用於做邊界檢查）。

using pii = pair<int, int>;
pii dir[4] = {pii(-1, 0), pii(1, 0), pii(0, -1), pii(0, 1)};

以上程式碼可解讀成下表：

索引	座標差	代表方向
0	(-1, 0)	往「上」走（row -1）
1	(1, 0)	往「下」走（row +1）
2	(0, -1)	往「左」走（col -1）
3	(0, 1)	往「右」走（col +1）

另外範例程式碼寫到了 vector<pii> last = {pii(si, sj)};，可用於避免上述所說的重複計算問題（同一個格子被不正確的累加多次）。

BFS

流水問題的程式碼即用 BFS 進行解題。

BFS 與 DFS 不同的點在於，BFS 是用「層次」搜尋，而非直直深入，請見下圖：

Image Source：https://zh-yue.m.wikipedia.org/wiki/File:Breadth-First-Search-Algorithm.gif

首先最上面的 root 為一層，往下一層有三個節點，再往下一層有四個節點。BFS 就是每一層進行搜尋，root 搜尋完後，就往下一層，把這三個節點遍歷一遍，再繼續往下一層，遍歷完這四個節點。

所以這也是為什麼 BFS 會被稱為廣度優先搜尋，他會一圈一圈的不斷擴大範圍，而非直直深入。

:::info
另外 BFS 的實作方式通常以 queue 資料結構進行實作。
:::

迷宮最短路徑

再見迷宮問題。

Problem : https://zerojudge.tw/ShowProblem?problemid=a982

上一篇中用了 DFS 去解這題，得出的結果是會 TLE，原因是 DFS 不適合拿來求最短路徑，DFS 以深度優先，一次就深入到底，基本上就是有勇無謀、橫衝直撞，當然它可能會找到一條路，但這條路有可能不是最短的。

BFS 會先搜尋離起點最近的點，也就是「走最少步」可以到的點，所以在當 BFS 第一次走到終點時，這條路就是最短的。

所以來看看 BFS 的程式碼要怎麼寫吧：

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

// pair 表示座標
using pii = pair<int, int>;

const int MAX_N = 100;

char maze[MAX_N][MAX_N]; // 迷宮地圖
bool visited[MAX_N][MAX_N]; // 訪問標記
int dist[MAX_N][MAX_N]; // 距離紀錄

int n;

// 上、下、左、右（方向位移）
pii dir[4] = {pii(-1, 0), pii(1, 0), pii(0, -1), pii(0, 1)};

// 判斷 (x, y) 是否可走
bool is_valid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n && // 邊界檢查
           maze[x][y] == '.' &&                 // 此路可走
           !visited[x][y];                      // 沒有走過
}

// bfs 函數：從 (start_x, start_y) 找到 (end_x, end_y) 的最短距離
int bfs(int start_x, int start_y, int end_x, int end_y) {
    queue<pii> q;                          // 宣告 bfs 用的佇列
    q.push({start_x, start_y});           // 把起點存入佇列
    visited[start_x][start_y] = true;     // 標記起點為已訪問的點
    dist[start_x][start_y] = 1;           // 距離初始設為 1（含起點）

    while (!q.empty()) {
        pii cur = q.front();              // 取得目前點
        q.pop();                          // 移除佇列前端
        int x = cur.first;
        int y = cur.second;

        // 若到達終點，立即回傳距離（最短路徑長度）
        if (x == end_x && y == end_y) {
            return dist[x][y];
        }

        // 試往四個方向移動
        for (int i = 0; i < 4; ++i) {
            int nx = x + dir[i].first;
            int ny = y + dir[i].second;

            if (is_valid(nx, ny)) {
                visited[nx][ny] = true;               // 標記為已訪問
                dist[nx][ny] = dist[x][y] + 1;        // 距離為前一格 + 1
                q.push({nx, ny});                     // 將新點加入佇列
            }
        }
    }

    return -1; // 若 BFS 結束仍未找到終點，代表無解
}

int main() {
    cin >> n;

    string line;

    for (int i = 0; i < n; ++i) {
        cin >> line;
        for (int j = 0; j < n; ++j) {
            maze[i][j] = line[j];
            visited[i][j] = false;
            dist[i][j] = 0;
        }
    }

    int result = bfs(1, 1, n - 2, n - 2);

    if (result == -1)
        cout << "No solution!" << endl;
    else
        cout << result << endl;

    return 0;
}

BFS vs DFS

比較項目	BFS	DFS
搜尋方式	逐層擴散（先搜尋鄰近節點）。	一路走到底。
使用資料結構	佇列。	遞迴或堆疊。
應用	1. 最短路徑（無權重圖） 2. 連通分量統計	1. 拓樸排序 2. 迷宮所有路徑列舉 3. 迴圈檢測
最短路徑適用與否	是（無權重情況）。	否（可能繞遠路）。
是否需記錄訪問過的節點	是，避免重複搜尋。	是避免無限遞迴。
演算順序	同一層節點全遍歷後才去下一層。	直接一條路到底，遇死路再回溯。

習題練習

1. Counting Rooms

Problem : https://cses.fi/problemset/task/1192

題目內容：

給定一張建築物的地圖，你的任務是數這棟建築物裡面有多少間房間。

地圖大小為 $n \times m$ 的方格，每個方格不是地面就是牆。你可以上下左右在這些地面的方格中移動。

輸入說明：

第一行輸入包含兩個整數 $n$ 和 $m$ ：分別為地圖的高和寬。

接下來有 n 行 m 個字元，用於描述這個地圖。每個字元不是 . （地面）就是 #（牆）。

輸出說明：

輸出一個整數：房間數。

限制條件：

• $1 \leq n, m \leq 1000$

範例輸入：

5 8
########
#..#...#
####.#.#
#..#...#
########

範例輸出：

3

這個所謂的房間呢，其實就是 . 的連通塊，所以上面有三間房間。

解題思路基本上跟之前都差不多，連通塊計算也是，就遍歷整張地圖，遇到 . 就呼叫一次 bfs，結束了就 room_count++。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

int n, m;
vector <string> grid;
vector <vector<bool>> visited;

pii dir[4] = {pii(-1, 0), pii(1, 0), pii(0, -1), pii(0, 1)};

void bfs(int sx, int sy){
    queue <pii> q;
    q.push(pii(sx, sy));
    visited[sx][sy] = true;
    
    while (!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        
        for (int i = 0; i < 4; ++i){
            int nx = x + dir[i].first;
            int ny = y + dir[i].second;
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m){
                if (!visited[nx][ny] && grid[nx][ny] == '.'){
                    visited[nx][ny] = true;
                    q.push(pii(nx, ny));
                }
            }
        }
    }
} 

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    cin >> n >> m;
    grid.resize(n);
    visited.assign(n, vector<bool>(m, false));

    for (int i = 0; i < n; ++i)
        cin >> grid[i];

    int room_count = 0;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (!visited[i][j] && grid[i][j] == '.') {
                bfs(i, j);
                room_count++;
            }

    cout << room_count;
    return 0;
}

2. 靈犬尋寶

Problem : https://tioj.ck.tp.edu.tw/problems/1143

嗯…這題需要動點腦，首先畫個二維平面座標圖，如下：

我知道很爛XD，這個當示意圖啦～

總之畫完後，再對照一下題目給的圖，可以發現靈犬每次移動會移動 $\sqrt{10}$ 單位，並且移動的前提是靈犬四周上下左右「一」單位內不能有障礙物，這樣才能移動。

解題思路基本上與一般 BFS 題目解題差不多，只是 dir 的部分要依照題目給的方向改一下，另外題目也有加上靈犬四周有障礙物就不能移動的條件，具體怎麼寫可以看範例程式碼。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100;

// 八個「√10 單位」跳躍的向量 (dx, dy)
// 分別對應題目圖示中的 1～8 號方向：
//  1: (+1,+3), 2: (-1,+3), 3: (-3,+1), 4: (-3,-1),
//  5: (-1,-3), 6: (+1,-3), 7: (+3,-1), 8: (+3,+1)
int dx[8] = {  1, -1, -3, -3, -1,  1,  3,  3 };
int dy[8] = {  3,  3,  1, -1, -3, -3, -1,  1 };

// 邊界檢查
bool in_bounds(int x, int y) {
    return x >= 0 && x < MAXN && y >= 0 && y < MAXN;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;

    // 建立 blocked[][]，標記每個格子是否有障礙物
    // blocked[x][y] = true 表示 (x,y) 無法通行
    bool blocked[MAXN][MAXN] = { false };
    for (int i = 0; i < n; i++) {
        int ox, oy;
        cin >> ox >> oy;
        // 將輸入的每個障礙物座標標為 blocked
        blocked[ox][oy] = true;
    }

    // 讀取起點 (sx, sy) 與終點 (tx, ty)
    int sx, sy, tx, ty;
    cin >> sx >> sy;    // 靈犬初始位置
    cin >> tx >> ty;    // 寶物位置

    bool visited[MAXN][MAXN] = { false };
    queue<tuple<int,int,int>> q; // queue 存放待處理節點 (x, y, dist)

    // 將起點加入佇列，距離 dist = 0
    q.emplace(sx, sy, 0);
    visited[sx][sy] = true;

    // bfs
    while (!q.empty()) {
        auto [x, y, dist] = q.front();
        q.pop();

        // 若當前座標即目標，輸出最少步數並結束
        if (x == tx && y == ty) {
            cout << dist;
            return 0;
        }

        // 試 8 個跳躍方向
        for (int d = 0; d < 8; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            // 邊界檢查：跳出格網就略過
            if (!in_bounds(nx, ny)) 
                continue;
            // 目標格若有障礙，則略過
            if (blocked[nx][ny]) 
                continue;

            // 檢查靈犬四周有無障礙物：
            // 上跳 (dy == +3)：檢查 A 點 (x, y+1)
            // 左跳 (dx == -3)：檢查 B 點 (x-1, y)
            // 下跳 (dy == -3)：檢查 C 點 (x, y-1)
            // 右跳 (dx == +3)：檢查 D 點 (x+1, y)
            int mx = x, my = y;
            if (dy[d] == +3) {
                my = y + 1;       // A 點
            } else if (dx[d] == -3) {
                mx = x - 1;       // B 點
            } else if (dy[d] == -3) {
                my = y - 1;       // C 點
            } else if (dx[d] == +3) {
                mx = x + 1;       // D 點
            }
            // 若靈犬四周有障礙就跳過
            if (blocked[mx][my]) 
                continue;

            // 若 (nx,ny) 尚未訪問，標記並加入佇列，距離 dist+1
            if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                q.emplace(nx, ny, dist + 1);
            }
        }
    }

    cout << "impossible";
    return 0;
}

後面的習題就不寫了，太燒腦XD。