前言

今天有兩題相關題目，希望大家可以透過這兩題更加熟悉 BFS 的應用、如何撰寫與實作細節

UVa 439 - Knight Moves

題目說明

有一面西洋棋的棋盤，問騎士從 X 走到 Y 最少需要走幾步

解題思路

簡單來說就是要走棋盤然後找最快路線，所以直接 BFS 就可以解決了

AC Code

#include<bits/stdc++.h>
using namespace std;
int dx[8] = {-1,-1,1,1,2,2,-2,-2},dy[8] = {2,-2,2,-2,1,-1,1,-1};
bool used[128][128];
int bfs(int sx,int sy,int ex,int ey){
    queue<pair<pair<int,int>,int>> q;
    for(int i = 0;i < 128;i++){
        for(int j = 0;j < 128;j++){
            used[i][j] = false;
        }
    }
    q.push({{sx,sy},0});
    used[sx][sy] = true;
    while(!q.empty()){
        pair<pair<int,int>,int> cur,nxt;
        cur = q.front();
        if(cur.first.first == ex && cur.first.second == ey){
            return cur.second;
            break;
        }
        q.pop();
        for(int i = 0;i < 8;i++){
            nxt = cur;
            nxt.first.first += dx[i];
            nxt.first.second += dy[i];
            nxt.second ++;
            if(nxt.first.first >= 'a' && nxt.first.first <= 'h' && nxt.first.second >= '1' && nxt.first.second <= '8' && !used[nxt.first.first][nxt.first.second]){
                if(nxt.first.first == ex && nxt.first.second == ey){
                    return nxt.second;
                    break;
                }
                used[nxt.first.first][nxt.first.second] = true;
                q.push(nxt);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s,e;
    while(cin >> s >> e){
        cout << "To get from " << s << " to " << e << " takes " << bfs(s[0],s[1],e[0],e[1]) << " knight moves.\n";
    }
    return 0;
}

UVa 10959 - The Party, Part I

題目說明

主人 Don Giovanni 有一場舞會，有個東西叫做 Don Giovanni number
計算方式如下：

• 沒有人的 Don Giovanni number 是負的
• Don Giovanni 自己的 Don Giovanni number 是 0
• 和 Don Giovanni 跳過舞的人他們的 Don Giovanni number 是 1 ，和 Don Giovanni number 是 n 的人跳過舞且沒有和 Don Giovanni number 比 n 小的人跳過舞的人，他們的 Don Giovanni number 是 n + 1
• 如果有人一直沒有和有 Don Giovanni number 的人跳舞，則他的 Don Giovanni number 是無限大，但是題目保證不會產生這種情形

要確定每一個人的 Don Giovanni number

解題思路

其實這題可以直接想成它是一張無向圖，然後要找出點對點的最短路徑，因此就是利用 BFS 找最短路徑的經典題型

AC Code

#include<bits/stdc++.h>
using namespace std;
int t,p,d,q[1050],dis[1050];
bool edge[1050][1050];
void bfs(){
    q[0] = 0;
    dis[0] = 0;
    int cur;
    for(int i = 0,j = 1;i < j;i++){
        cur = q[i];
        for(int nxt = 0;nxt < p;nxt++){
            if(edge[cur][nxt] && dis[nxt] > dis[cur] + 1){
                dis[nxt] = dis[cur] + 1;
                q[j] = nxt;
                j++;
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    int c = 0;
    while(t--){
        if(c){
            cout << "\n";
        }else{
            c++;
        }
        for(int i = 0;i < 1050;i++){
            dis[i] = 1e9 + 10;
            for(int j = 0;j < 1050;j++){
                edge[i][j] = false;
            }
        }
        cin >> p >> d;
        int a,b;
        for(int i = 0;i < d;i++){
            cin >> a >> b;
            edge[a][b] = edge[b][a] = true;
        }
        bfs();
        for(int i = 1;i < p;i++){
            cout << dis[i] << "\n";
        }
    }
    return 0;
}

實作細節

其實 BFS 有些題目會需要回朔路線，所以我上面有寫了一種是利用內建的 queue 來寫，一種是利用陣列模擬 queue，陣列模擬的用意是如果要回朔可以利用 index 去往回找路線，而如果用內建的 queue 來做會發現會有一直 pop 的動作，所以會比較難回朔，因此要看題目類型再決定要用什麼方式寫

總結

這兩題有一題是基本的 BFS，另一題是比較不明顯看出的經典題，所以其實有些題目如果有辦法把它弄成一張圖就有機會可以利用 BFS 求解，這部分就是要有比較多的思考了，希望這兩題可以讓大家學到 BFS 的一些實作細節與題目思考邏輯