# BFS

就BFS

---

## 1. 什麼是 BFS？為什麼能找最短路？

相信各位沒玩過 Minecraft 應該也看過
想像你在 Minecraft 的地上到了一盆水，那那個水會從中心慢慢往外擴散。
- 第 `0` 格：水源位置（起點）
- 第 `1` 格：一步可達
- 第 `2` 格：兩步可達
- 以此類推…

如果地上有牆或玻璃（障礙），水就過不去必須要用繞的。而哪一格最先被水淹到，代表他離起點的步數最少。
BFS（Breadth-First Search，廣度優先搜尋）的實作原理就像是這樣，從中心一步一步往外擴散。


---

正式一點來說：
- 從中心開始每走一步都算 `1`（沒有快慢之分，除非題目特別要求）
- `BFS` 會先把距離 `1` 的格子全部處理完，再處理距離 `2`、距離 `3`…
- 所以「第一次」碰到目標時，距離必然是最短步數。

這就是為什麼 `BFS` 能解最短路。

寫 `BFS` 的三個重點：
- 用之前在 `STL` 上過的 `queue`（先進先出，就像一排人一個一個往外擴）
- 入隊時就標記「來過了」（避免重複入隊）
- 一摸到終點就收工（第一次碰到一定會是最短的）

---

## 2. BFS vs DFS

- BFS：一圈一圈灑出去，像水流。第一次碰到目標就是最短。
- DFS：沿著一條路一直鑽到底，可能先繞遠路才遇到目標，不保證最短。

要找最短路 → 用 `BFS`。
想要找「有沒有路」或「整個形狀」 → 用 `DFS`。

白話點就是如果題目有要求最短路，基本上第一個要想到的是 `BFS` ，不過其實大多數能用 `BFS` 的題目 `DFS` 也可以，反過來也是，但就是好不好寫跟速度的差別。

另一個判斷的方式是，通常 `DFS` 都會寫到遞迴找路，而 `BFS` 就不會。

---

## 3. 例題：b348: nowob的機廳冒險

題意可以過去看一下(這次我題目沒搞事了，應該比較好懂)

地圖說明（四方向移動：上、下、左、右）：
- 0：空氣
- 1：nowob 起點（只有一個）
- 2：maimai（可能很多個）
- 3：地雷女（障礙，不能走）

要做的事：
- 輸出：從起點走到最近一台 maimai 的最短步數
- 若走不到任何 maimai，輸出 `-1`

---

移動規則：
- 只能上下左右走一格（四方向），不能走斜的(真的跟Minecraft的水一樣)
- 不能走出地圖外(就判一下邊界)
- 不能走進 `3`（不然就要上靠北版了）
- 可以走在 `0`
- 踩到 `2` 就代表到達一台 maimai，直接輸出然後return 0;

---

距離怎麼算？
- 起點站著不動是 0 步
- 往相鄰的一格走是 1 步
- 再走一格就是 2 步，以此類推
- 你要輸出的就是「到第一台maimai的最少步數」

---

什麼時候輸出 -1？
- 地圖上根本沒有 `2`
- 或者所有 `2` 都被 `3` 擋住，起點就算繞路也到不了

---

### 看一個範例（一步一步看懂）

範例輸入：

5 6
0 0 0 0 0 0
0 1 0 3 0 0
0 3 0 3 2 0
3 0 3 0 0 0
0 2 0 0 0 2

---

你會看到：
- 起點 `1` 在第 2 行第 2 列（從 `0-based` 數的話是 (1,1)）
- 有好幾個 `2`（maimai），像 (2,4)、(4,1)、(4,5)
- 其中一條最短路：右、上、右、右、下、下
- 走了 6 步，答案就是 6
- 你不需要輸出路徑，只要輸出步數就好

---

### 這題要怎麼下手

一樣把 `BFS` 當作水在擴散，照這樣做：

1. 先把整張地圖讀進來，找到起點 `1` 的位置 (sr, sc)
2. 準備一張「距離表」`dist`，先全部設成 -1（代表還沒來過）
3. 把起點丟進 `queue`，並把 dist[sr][sc] 設成 0
4. 進入迴圈：
- 從 `queue` 拿出一格 (r, c)
- 往四個方向看 (nr, nc)
- 如果越界、或那格是 `3`、或 `dist` 不是 -1（來過了），就略過
- 否則把 dist[nr][nc] = dist[r][c] + 1，並把這格丟進 `queue`
- 如果這格剛好是 `2`，立刻輸出 dist[nr][nc]，結束（第一次遇到 = 最短！）
5. `queue` 都清空了還沒遇到 `2`，就輸出 `-1`

---

你可以把它想成：
- 0 步：只有起點
- 1 步：離起點一格的所有位置
- 2 步：離起點兩格的所有位置
- …
- 哪一層第一次踩到 `2`，那層數就是答案

---
基本上 `BFS` 就是這樣，雖然會有很多變體但本身邏輯差不多，不過偷偷講一下，`BFS` 不會是最短路的最佳解，至於怎麼做最佳解可以來參加下學期的進階班:D

---