---
# System prepended metadata

title: 【C++】競程筆記（BFS：廣度優先搜尋）
tags: [程式設計, C++, 競程, 演算法, 程式語言, CP, BFS]

---

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

[TOC]

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

流水問題
---

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

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

![image](https://hackmd.io/_uploads/HyQMtqwrxl.png)

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

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

以下是有關這個流水問題的範例程式碼（From : [NTUCPC Guide | BFS](https://guide.ntucpc.org/AlgorithmTechnique/bfs/)）：

```cpp=
// 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 用於做邊界檢查）。

```cpp=
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 是用「層次」搜尋，而非直直深入，請見下圖：

![Breadth-First-Search-Algorithm](https://hackmd.io/_uploads/BJSPJiDBxl.gif)

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 的程式碼要怎麼寫吧：

```cpp=
#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. 最短路徑（無權重圖）<br> 2. 連通分量統計  | 1. 拓樸排序<br> 2. 迷宮所有路徑列舉<br> 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++`。

範例程式碼：

```cpp=
#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

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

![image](https://hackmd.io/_uploads/S1chEJuHgx.png)

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

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

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

範例程式碼：

```cpp=
#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。