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

---