# 廣度優先搜尋 Breadth First Search, BFS

相對於一找到路總之先往下走再說的 DFS，
BFS 會優先探索完最近的所有地點，再慢慢擴大移動範圍。

更精確地說，BFS 會優先探索完所有距離起點 $i-1$ 步以內的地點後，
才會開始探索距離起點 $i$ 步的地點。

這個特性使得 BFS 相對適合尋找「從起點到任意地點最少要走幾步」，
但就不擅長找所有的不同走法。

:::info
需要找有多少種不同走法或結果，通常使用 DFS；
需要找距離目標最少要走幾步，則通常使用 BFS。
:::

## 走迷宮的例子

:::success
### 走迷宮問題
給一個 $n\times m$ 大小的迷宮，以「`#`」代表不可通行的障礙物，
「`.`」代表可通行的空間，「`S`」代表起點、「`E`」代表終點，
每花 $1$ 分鐘可走到「上、右、下、左」四個方向其中一個相鄰、且可通行的地方。
絕對不能走到地圖外面。
求從起點走到終點最少要花多少分鐘，如果不可能達成則輸出「$-1$」。

#### 範例輸入

5 6
S....#
##.##.
...#..
..#...
....#E

#### 範例輸出

13

#### 範例輸入

3 5
#...S
#.##.
.#.E#

#### 範例輸出

-1

:::

這類題目對 DFS 而言，途中難以避免繞路，走到終點時無法確保目前走法最佳，
還得回頭找其它走法，效率會非常低。

BFS 會先探索並標記出所有 $0$ 步可到的位置（即起點，標記為 $0$）：

0....#
##.##.
...#..
..#...
....#E

從 $0$ 步的位置找出所有相鄰位置，即為 $1$ 步所能走到的地方：

01...#
##.##.
...#..
..#...
....#E

從 $1$ 步的位置找出所有相鄰位置，即為 $2$ 步所能走到的地方：

012..#
##.##.
...#..
..#...
....#E

從 $2$ 步的位置找出所有相鄰位置，即為 $3$ 步所能走到的地方：

0123.#
##3##.
...#..
..#...
....#E

如此一步步反覆至探索出終點為止（以 $A$ 到 $D$ 代表 $10$ 到 $13$）：

01234#
##3##.
654#CD
76#ABC
8789#D

由於 BFS 先近再遠的特性，當首次踏上任意點 $(x, y)$ 時，
如果是第 $i$ 步，那代表了從 $0$ 到 $i-1$ 步完全踏不上 $(x, y)$。
既然不存在更小步數的解，可判斷起點至 $(x, y)$ 的最小步數為 $i$。

那麼，每個點就只需被探索到一次，就能確定最小步數，不必再看第二次。
基於此特性，首次踏上終點 $(E_x, E_y)$ 時的步數，即為起點至終點最小步數。

### 實作 Implementation

實作上會從起點開始，由近到遠按順序探索。
嘗試用多條陣列，第 $i$ 條陣列記錄離起點 $i$ 步的所有情形：

0 步：(0, 0)

窮舉所有 $0$ 步的情形，檢查是否為終點，並找出所有 $1$ 步可到的地點：

0 步：(0, 0)  <==
1 步：(0, 1)  (NEW!!)

窮舉所有 $1$ 步的情形，檢查是否為終點，並找出所有 $2$ 步可到的地點：

0 步：(0, 0)
1 步：(0, 1)  <==
2 步：(0, 2)  (NEW!!)

窮舉所有 $2$ 步的情形，檢查是否為終點，並找出所有 $3$ 步可到的地點：

0 步：(0, 0)
1 步：(0, 1)
2 步：(0, 2)  <==
3 步：(0, 3), (1, 2)  (NEW!!)

觀察過程，會發現只要按找到的順序一個一個看，到第 $i$ 步的時候，
就已保證看過所有第 $i-1$ 步的地點，因此所有第 $i$ 步的地點皆已被找到；
而後續會找到的新地點全為 $i+1$ 步的，可知第 $i+1$ 步所有地點，
均會在所有第 $i$ 步之後才被找到。

由歸納法可證，使用一個 queue 來依序存放所有地點，
即可維持步數的單調性，無需使用多條陣列來分存不同步數的地點，
也不會打亂遠近的順序。

整理步驟如下：

- 將所有起點先放到 queue 中
- 從 queue 依序拿出每個點，對於每個點：
- 檢查是否為終點；如果是，則 BFS 結束
- 窮舉所有可以走到、可通行的相鄰點：
- 如果還未被探索過，則放進 queue 並記錄為已探索

:::spoiler 實作參考

int n, m;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
string board[1024];

struct node
{
    int x, y;
    int dis;
};

node qq[1048576];
bool used[1024][1024];

int bfs(int sx, int sy, int ex, int ey)
{
    int i, j, k;
    node cur, nxt;
    memset(used, 0, sizeof(used));
    // 將所有起點放進 queue 中
    qq[0].x = sx;
    qq[0].y = sy;
    qq[0].dis = 0;
    // 先將所有起點標記為「已探索」
    used[sx][sy] = true;
    // 依序看過 queue 中所有的點
    // i 為目前要看的點；j 為新的點進來時要放的空白位置
    for (i=0, j=1; i<j; i++)
    {
        cur = qq[i];
        // 檢查是否為終點
        if (cur.x == ex && cur.y == ey)
        {
            // 如果是，回報最小步數
            return cur.dis;
        }
        // 窮舉上下左右四個方向，尋找可通行地點
        for (k=0; k<4; k++)
        {
            nxt = cur;
            nxt.x += dx[k];
            nxt.y += dy[k];
            nxt.dis++;
            // 最優先檢查是否在範圍內，以防存取到不正常的陣列 index
            if (nxt.x >= 0 && nxt.x < n
                && nxt.y >= 0 && nxt.y < m)
            {
                // 確定在範圍內，才檢查是否可通行和是否已探索
                if (board[nxt.x][nxt.y] != '#'
                    && !used[nxt.x][nxt.y])
                {
                    // 設為已探索並加入 queue 中
                    used[nxt.x][nxt.y] = true;
                    qq[j] = nxt;
                    j++;
                }
            }
        }
    }
    // 如果找過所有可探索範圍，未能發現終點，即為無解
    return -1;
}

:::

所有地點至多被加入 queue 一次，因此 queue 最大長度與地點數一致；
每個地點窮舉 $4$ 個相鄰方向，複雜度為 $n\times m\times 4 = O(nm)$

### 實作常見錯誤：關於 used

複雜度 $O(nm)$ 建立於每個點只被加入 queue 恰一次的前提，
如果沒有 used 或設錯，會讓 bfs 劣化至指數複雜度 $O(4^{nm})$。

且 used 必須在一加入 queue 就設，而「**不該**」在拿出來時才設。
到被拿出來看時，可能已被加入複數次，這些又會再往下擴展相同的點複數次。

:::warning
筆者曾在全國賽因漏加 used 而在答案正確的情況下 TLE 掉一整題，
因沉痛的教訓而印象特別深刻。希望各位不用在痛過後才記取此教訓。
:::

### 實作常見錯誤：在加入 queue 時檢查是否為終點

在加入 queue 時檢查終點，可能讓我們可以少看一些點，較快發現終點；
但影響並沒有大到能影響複雜度，卻可能忽略掉「起點即終點」的情形。
即使這題同一格無法同時存在「S」和「E」，但別的問題有可能。

:::warning
雖能將「起點即終點」作為特例判斷，但出錯的風險相對較大；
能避免特例就最好盡量避免，犧牲的計算量是微不足道的。
:::

### 想想看

如果存在複數個終點，只需從起點到達任一終點皆可，該如何處理呢？
複雜度又會如何變化呢？

### 想想看之二

如果存在複數個起點，只需從任意起點出發、到達任一終點，求最小距離時，
又該如何處理呢？複雜度會如何變化呢？

## 歡樂練習時間

:::success
### TOJ 432 - Akechi 明智的選擇
https://toj.tfcis.org/oj/pro/432/
:::

:::success
### UVa 439 - Knight Moves
http://domen111.github.io/UVa-Easy-Viewer/?439
:::

:::success
### UVa 532 - Dungeon Master
http://domen111.github.io/UVa-Easy-Viewer/?532
:::

:::success
### UVa 10102 - The path in the colored field
http://domen111.github.io/UVa-Easy-Viewer/?10102
:::

:::success
### UVa 10959 - The Party, Part I
http://domen111.github.io/UVa-Easy-Viewer/?10959
:::

:::success
### UVa 11352 - Crazy King
http://domen111.github.io/UVa-Easy-Viewer/?11352
:::

{%hackmd @sa072686/__style %}

###### tags: `競程：三章`, `競程`