【圖論】BFS 廣度優先搜尋演算法

發布於 更新於 分類於 ， 閱讀次數： 文章字數： 392 所需閱讀時間 ≈ 1 分鐘

簡介

在競程中，常有幾種形式出現 BFS 題目，包括但不限於圖論的 Array、Tree 等。

原理

通常以 Queue 來實現 BFS。若找到此處為可走路徑，則加入其出邊至 Queue 容器（要判斷是否為邊界、是否走過）。

例子

第一行輸入一個 N(1<=N<1000)N(1<=N<1000) 值，表示圖為 N*N 的陣列。

2 ~ N+1 行為輸入的圖，僅包含 #、. 前者表示牆壁，後者表示可走路徑，超出邊界亦視為牆壁。

Sample Input:

1
2
3
4
5
6
7
8
9
10
9
#########
#...#####
#.#.##.##
#...#####
#####..##
##.##..##
##.##..##
##.######
######...

請輸出可走路徑的總個數。（我不知道怎麼描述）

Sample Output:

1
5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define ouo ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define db double
using namespace std;

string str;
int n, cnt = 0;
int g[1005][1005] = {0};
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void bfs() {
    queue<pair<int, int>> que;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] == 1) {
                que.push({i, j});
                // when loop finds availible path, cnt add 1
                cnt++;
                
                // BFS
                while (!que.empty()) {
                    auto now = que.front();
                    que.pop();
                    
                    // when it checked, fix it to 0
                    g[now.first][now.second] = 0;
                    
                    // check for next 4 direction
                    for (int k = 0; k < 4; k++) {
                        int x = now.first + dx[k];
                        int y = now.second + dy[k];

                        if (x >= 0 && x < n && y >= 0 && y < n && g[x][y]) {
                            que.push({x, y});
                        }
                    }
                }
            }
        }
    }
}

int main() {
    // init
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> str;
        for (int j = 0; j < n; j++) {
            if (str[j] == '.') g[i][j] = 1;
        }
    }
    
    // BFS
    bfs();
    
    // print count
    cout << cnt << "\n";

    return 0;
}

練習題

  • CSES Counting Rooms
  • CSES Labyrinth
  • ZeroJudge d365. 10336 - Rank the Languages
  • ZeroJudge d406. 倒水時間
  • ZeroJudge k205. 蝸牛的踩地雷攻略 1 (插旗)
  • ZeroJudge k615. 蝸牛的踩地雷攻略 2 (掃雷)
  • ZeroJudge n700. 蝸牛的踩地雷攻略 3 (點方塊)