# BFS(廣度優先搜尋)
## 複習：實作queue&pair

#include <iostream>
#include <queue>
using namespace std;

#define F first  //定義F為first S為second
#define S second //define可以使程式簡短

int main(){
    queue<pair<int, int>> q;

    for(int i = 1; i <= 5; i+=2){
        q.emplace(i, i+1); //相當於 q.push({i, i+1});
    }

    while(!q.empty()){
        auto tmp = q.front(); //自動設定資料型態  (此為pair<int, int>)
        cout << tmp.F << ' ' << tmp.S << '\n'; //輸出first跟second
        
        /*
        也可寫成：
        auto [a, b] = q.front(); //將a = q.front().first, b = q.front().second
        cout << a << ' ' << b << '\n';
        */

        q.pop();
    }

    return 0;
}

:::spoiler 輸出

1 2
3 4
5 6

:::

## BFS概念說明
BFS是一種演算法(解題的方法)，精隨為藉由慢慢擴展的方式，來找到起點對於每個點的最短路徑
*也有一種說法叫淹水，慢慢地淹過每一格*
實際運作過程如下圖所例 ||(source: trt4497)||

## BFS實作
實作範例：
#### 輸入
第一行輸入一正整數 $N \leq 20$表示$N * N$的地圖
接下來有$N$行，每一行有$N$個數字$w_1, w_2, ... , w_n \in (0, 1)$
$w_i = 0$ 代表該格不能通過

#### 輸出
輸出一個正整數 $s$ 代表從左上$(0, 0)$走到右下$(n-1, n-1)$的最短步數
### 思路
我們可以明顯地觀察到需要使用BFS來計算最短路徑
而BFS的實作順序為 新增起點 $\rightarrow$ 遍歷地圖```mp```$*_{(1)}$ $\rightarrow$ 輸出右下角```cnt```數值即為最短路徑

---
*$_{(1)}$：
1. 取得現在位置座標 $(y,\ x)$ 並從```queue```中移除
2. 往四個方向擴展 $\rightarrow$ 另存新座標 $(ny,\ nx)$
3. 判斷是否超出地圖範圍 ($0 \leq x,\ y < 20$)、```used```是否走過、```mp[ny][nx]```是否不能通過
4. ```used```陣列標記走過```= 1```、路徑長```cnt```陣列```+ 1```、合法座標放入```queue```中
---
### 版本1 (四個if判斷)
:::spoiler Code

#include <iostream>
#include <queue>
using namespace std;


int mp[50][50];
int used[50][50] = {0}, cnt[50][50] = {0}; //all = 0

int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> mp[i][j];
        }
    }

    queue<pair<int, int>> q;
    q.emplace(0, 0); //start

    while(!q.empty()){
        auto [y, x] = q.front();
        q.pop();
        
        for(int i = 0; i < 4; i++){ //4 dir
            if(i == 0){//up
                int ny = y - 1, nx = x;
                if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue; //out
                if(used[ny][nx]) continue; //used before
                if(mp[ny][nx] == 0) continue; //cant pass

                used[ny][nx] = 1; //used
                cnt[ny][nx] = cnt[y][x] + 1;
                q.emplace(ny, nx);
            }else if(i == 1){//down
                int ny = y + 1, nx = x;
                if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue; //out
                if(used[ny][nx]) continue; //used before
                if(mp[ny][nx] == 0) continue; //cant pass

                used[ny][nx] = 1; //used
                cnt[ny][nx] = cnt[y][x] + 1;
                q.emplace(ny, nx);
            }else if(i == 2){//left
                int ny = y, nx = x - 1;
                if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue; //out
                if(used[ny][nx]) continue; //used before
                if(mp[ny][nx] == 0) continue; //cant pass

                used[ny][nx] = 1; //used
                cnt[ny][nx] = cnt[y][x] + 1;
                q.emplace(ny, nx);
            }else if(i == 3){//right
                int ny = y, nx = x + 1;
                if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue; //out
                if(used[ny][nx]) continue; //used before
                if(mp[ny][nx] == 0) continue; //cant pass

                used[ny][nx] = 1; //used
                cnt[ny][nx] = cnt[y][x] + 1;
                q.emplace(ny, nx);
            }
        }

        if(cnt[n-1][n-1] != 0){
            cout << cnt[n-1][n-1];
            break;
        }
    }
}

:::
### 版本2 ($dx, dy$ 陣列)
根據上個版本，我們可以發現一個問題：~~程式碼又臭又長~~，且易讀性差
所以我們可以針對四個方向的遍歷去改良
新增一個 $\Delta x$ 陣列與一個 $\Delta y$ 陣列，分別儲存改變方向時對於座標的加數(可能為負)
經過此操作後，我們只需要每次呼叫 $\Delta x$、$\Delta y$ 中的每一項資料，與 $x,\ y$ 做加法運算即可

:::spoiler Code

#include <iostream>
#include <queue>
using namespace std;

int mp[50][50];
int used[50][50] = {0}, cnt[50][50] = {0}; //all = 0

int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1}; //up down left right

int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> mp[i][j];
        }
    }

    queue<pair<int, int>> q;
    q.emplace(0, 0);

    while(!q.empty()){
        auto [y, x] = q.front();
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i], nx = x + dx[i]; //change dir

            if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
            if(used[ny][nx]) continue;
            if(mp[ny][nx] == 0) continue;

            used[ny][nx] = 1;
            cnt[ny][nx] = cnt[y][x] + 1;
            q.emplace(ny, nx);
        }

        if(cnt[n-1][n-1] != 0){
            cout << cnt[n-1][n-1];
            break;
        }
    }
}

:::

## 練習題
### [Zerojudge- a982 迷宮問題#1](https://zerojudge.tw/ShowProblem?problemid=a982)
:::spoiler 起點? 終點?
注意題目的座標表示方式
:::

:::spoiler 到不了終點
圖跑完程式會接到哪? 輸出就放在那
前面如果到的了要直接終止程式
:::

:::spoiler AC Code

#include <iostream>
#include <queue>
using namespace std;

#define pii pair<int, int>

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int main(){
    int n; cin >> n;
    char mp[105][105];
    int used[105][105] = {0}, cnt[105][105] = {0};

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> mp[i][j];
        }
    }

    queue<pii> q;
    q.emplace(2, 2);
    cnt[2][2] = 1;
    used[2][2] = 1;

    while(!q.empty()){
        auto [y, x] = q.front(); q.pop();
        if(y == n-1 && x == n-1){
            cout << cnt[y][x];
            return 0;
        }
        
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < 4; j++){
                int ny = y + dy[i], nx = x + dx[i];
                if(ny < 1 || ny > n || nx < 1 || nx > n) continue;
                if(used[ny][nx]) continue;
                if(mp[ny][nx] == '#') continue;

                used[ny][nx] = 1;
                cnt[ny][nx] = cnt[y][x] + 1;
                q.emplace(ny, nx);
            }
        }
    }

    cout << "No solution!";
    return 0;
}

:::
### [Zerojudge- d406 倒水時間](https://zerojudge.tw/ShowProblem?problemid=d406)
:::spoiler 往上流
注意處理題目輸入，處理方向的時候排除```上```
:::
:::spoiler 起點位置
保證到水位置只會在 $y = 0$ 的時候 且只有一個$1$
:::
:::spoiler 若干筆測資

while(cin >> s)

注意輸出格式
:::
:::spoiler AC Code

#include <iostream>
#include <queue>
using namespace std;

#define pii pair<int, int>

int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

int main(){
    int s, Case = 0;

    while(cin >> s){
        Case++;
        int n, m; cin >> n >> m;
        int mp[105][105];
        int used[105][105] = {0}, cnt[105][105] = {0};
        queue<pii> q;
        bool flag = false;

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> mp[i][j];
                if(!flag && mp[i][j] == 1){
                    q.emplace(i, j);
                    cnt[i][j] = 1;
                    used[i][j] = 1;
                    flag = true;
                }
            }
        }

        while(!q.empty()){
            auto [y, x] = q.front();
            q.pop();

            for(int i = 0; i < 4; i++){
                if(i == 0 && s == 2) continue; //skip up(s = 2)

                int ny = y + dy[i], nx = x + dx[i];
                if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                if(used[ny][nx]) continue;
                if(mp[ny][nx] == 0) continue;

                used[ny][nx] = 1;
                cnt[ny][nx] = cnt[y][x] + 1;
                q.emplace(ny, nx);
            }
        }
        
        cout << "Case " << Case << ":\n";
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cout << cnt[i][j] << ' ';
            }
            cout << "\n";
        }
    }
}

:::
### [Zerojudge- d453 最短距離](https://zerojudge.tw/ShowProblem?problemid=d453)
:::spoiler 輸入方式
用字串或字元存取(無空格)
:::
:::spoiler 起點終點
不一定固定 需要調整
直接判斷是否到終點並輸出```cnt```
:::
:::spoiler AC Code

#include <iostream>
#include <queue>
using namespace std;

#define pii pair<int, int>
#define F first
#define S second

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main(){
    int N; cin >> N;
    while(N--){
        int n, m, y1, x1, y2, x2; cin >> n >> m >> y1 >> x1 >> y2 >> x2;
        pii bg = make_pair(y1-1, x1-1), ed = make_pair(y2-1, x2-1);

        queue<pii> q; q.push(bg);
        char mp[105][105];
        int used[105][105] = {0}, cnt[105][105] = {0};

        used[bg.F][bg.S] = 1;
        cnt[bg.F][bg.S] = 1;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> mp[i][j];
            }
        }

        int flag = 0;
        while(!q.empty()){
            auto [y, x] = q.front(); q.pop();
            if(y == ed.F && x == ed.S){
                cout << cnt[y][x] << "\n";
                flag = 1;
                break;
            }
            for(int i = 0; i < 4; i++){
                int ny = y + dy[i], nx = x + dx[i];
                if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                if(used[ny][nx]) continue;
                if(mp[ny][nx] == '1') continue;

                used[ny][nx] = 1;
                cnt[ny][nx] = cnt[y][x] + 1;
                q.emplace(ny, nx);
            }
        }

        if(!flag) cout << "0\n";
    }
    return 0;
}

:::
### [CSES- Counting Rooms](https://cses.fi/problemset/task/1192)
:::spoiler 題譯
有一個$N * M$的建築地圖，你需要計算其中有幾個房間，你可以往上下左右行動

*#輸入*
第一行有兩個正整數$N \ M(1 \leq N, M \leq 1000)$ 表示圖的長度和寬度
接下來有$N$行，每行$M$個字元$c_1, c_2, ...,c_m \in (.,\#)$，$.$ 為地板，$\#$ 為牆壁

*#輸出*
輸出一個正整數表示房間的數量
:::
:::spoiler AC Code

#include <iostream>
#include <queue>
using namespace std;
 
#define F first
#define S second
 
char mp[1005][1005];
bool used[1005][1005] = {0};
int n, m, ans = 0;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> mp[i][j];
            if(mp[i][j] == '.'){
                v.emplace_back(i, j);
            }
        }
    }
    
    for(auto i : v){
        if(!used[i.F][i.S]){
            pair<int, int> tmp = i;
            ans++;
            queue<pair<int, int>> q;
            q.emplace(tmp);
            while(!q.empty()){
                auto [nx, ny] = q.front(); q.pop();
                for(int i = 0; i < 4; i++){
                    int x = nx + dx[i], y = ny + dy[i];
                    if(x < 0 || x >= n || y < 0 || y >= m) continue;
                    if(used[x][y]) continue;
                    used[x][y] = true;
                    if(mp[x][y] == '.') q.emplace(x, y);
                }
            }
        }
    }
 
    cout << ans;
    return 0;
}

:::
### 變體題：[CSES- Labyrinth](https://cses.fi/problemset/task/1193)
~~不想弄題譯~~
:::spoiler 起點終點
處理輸入時同時判斷
:::
:::spoiler 回溯?
找到一條最佳路徑後 要怎麼儲存行走的方向?
答案是再創一個陣列```parents```儲存來時的座標
:::
:::spoiler AC code

#include <bits/stdc++.h>
using namespace std;
 
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
pair<int, int> parents[1005][1005];
 
int main(){
    cin.tie(0) -> sync_with_stdio(0);
    char mp[1005][1005];
    bool used[1005][1005];
    memset(used, 0, sizeof(used));
    memset(parents, 0, sizeof(parents));
    queue<pair<int, int>> q;
    int n, m; cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> mp[i][j];
            if(mp[i][j] == 'A') {q.emplace(i, j); used[i][j] = 1; parents[i][j] = {-1, -1};}
        }
    }
 
    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(used[nx][ny] || mp[nx][ny] == '#') continue;
            used[nx][ny] = 1;
            parents[nx][ny] = {x, y};
            //cout << nx << " " << ny << "\n";
            q.emplace(nx, ny);
            if(mp[nx][ny] == 'B'){
                int cnt = 0;
                cout << "YES\n";
                string ans = "";
                while(true){
                    auto [tmpx, tmpy] = parents[nx][ny];
                    if(tmpx == -1) break;
                    cnt++;
                    
                    if(tmpx < nx) ans += "D";
                    else if(tmpx > nx) ans += "U";
                    else if(tmpy < ny) ans += "R";
                    else ans += "L";
 
                    nx = tmpx, ny = tmpy;
                }
                reverse(ans.begin(), ans.end());
                cout << cnt << "\n" << ans;
                return 0;
            }
        }
    }
 
    cout << "NO";
}

:::