【C++】競程筆記（BFS：廣度優先搜尋）
===
[TOC]
程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。
流水問題
---
以 NTUCPC Guide 舉的例子來說的話，水流只能往上下左右流，而且是同時流，然後求每個空地格子幾秒後會有水。
具體做法是先將流水的起點定為 0 秒，之後向上下左右擴散一單位的水並 + 1 秒，注意這邊要做邊界檢查，如下圖的第三張。
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 是用「層次」搜尋，而非直直深入，請見下圖：
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
嗯...這題需要動點腦，首先畫個二維平面座標圖，如下：
~~我知道很爛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。
Sign in with Wallet
Connect another wallet