# BFS 介紹
大一上學期的時候大家學過遞迴，這學期老師教倒水問題的時候也提過可以用遞迴來解這個問題。
BFS是對這類問題用不一樣的角度來思考，在某些情況下BFS會有比較好的效率；比如說要找**最小**值。

## 倒水問題
倒水問題的解法簡單來說是這樣：對於一個*狀態*，判斷它有沒有達到要求；如果沒有，找出所有可以從這個狀態*衍生*出的所有狀態，一個個遞迴下去檢查。

用倒水問題的說法來說，就是看現在的*水量*是不是答案；如果不是的話，對現在的這個水量進行*所有倒水的操作*（把A倒給B，把B倒給A，把A倒空...等），對所有新形成的水量**遞迴**下去問相同的問題。

## BFS概念
這類問題一開始會有一個*初始狀態*。**第一輪**先把所有對初始狀態進行**一次**操作之後可以形成的狀態找出來檢查；**第二輪**把所有第一輪的狀態進行一次操作之後（從初始狀態進行**兩次**）可以形成的狀態找出來檢查。以此類推，一直做到找到答案為止。
如果我們在第*N*輪找到目標狀態，那要達到目標狀態的最少操作次數就是*N*。（大家可以想一下為什麼）

而在這個過程中，如果搜尋到了一個以前**已經出現過**的狀態，那我們可以直接**跳過**，不用再重複搜尋（這點和遞迴找答案的時候一樣）。

## BFS 解倒水問題
*初始狀態*就是一開始兩個杯子A,B裏面各有多少水。
先檢查現在的水量是不是就是答案

if (A == ans) or (B == ans) :
    min_step = 0

**第一輪**：對一開始的狀態，窮舉所有可能的操作，對他們一一檢查。

if (A+B == ans) or (A-B == ans) or ... :
    min_step = 1

**第二輪**：對第一輪的每個狀態，窮舉所有可能的操作，對他們一一檢查。
...
**第N輪**：對第N-1輪的每個狀態，窮舉所有可能的操作，對他們一一檢查。

if ... or ... or ... :
    min_step = N

## 實作（C++）
STL有個container叫作`queue`，我們可以利用他輕鬆的達到目標。
把*初始狀態*放進queue。
**把`queue`的第一個人拿出來。** 看看它符不符合答案

auto x = Q.front();
Q.pop();
if (x.A == target || x.B == target) {
    min_step = x.step;
    break;
}

如果它不符合，對它窮舉所有可能的操作，一個個**放進`queue`**。

for all possible y derived from x {
    y.step = x.step + 1;
    Q.push(y);
}

持續做到**queue變空**為止。如果做到queue變空還是沒有找到答案，那就代表無解。

思考一下這為什麼可以work：因為把東西放進queue的順序是按照`step`**由小到大**，所以一旦發現一個`step`等於K的答案，`step`小於K的狀態一定都被檢查過了！

---

所以大概的程式碼可能會長這樣子：

struct S {...}; // 狀態
queue<S> Q;
Q.push(初始狀態);
while (!Q.empty()) {
    S x = Q.front();
    Q.pop();
    if (x已經出現過) continue;
    ... // 把x出現過這件事記起來
    if (x是答案）{
        min_step = x.step;
        break;
    }
    else {
        for (每個可行的操作 op) {
            S y = some_operation(x, op); // y是可以從x衍生出的一個狀態
            ...
            y.step = x.step+1;
            Q.push(y);
        }
    }
}
cout << min_step << endl;

## 應用
BFS 除了可以用來解倒水問題，也可以用來解走迷宮之類的問題（問最少幾步可以到終點）。
把起點當成*初始狀態*，終點當成*目標狀態*。可行的操作就是上下左右移動。
或者也可以反過來做，把*終點和起點的角色互換*，如果題目改成**起點唯一，但終點不只一個**（作業是不是跟這個有點像？），這樣會有不小的幫助~