Fork me on GitHub

广度优先搜索

发表于 | 更新于 | 分类于

基本概念

广度优先搜索算法（英语：Breadth-First-Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。

例题：被围绕的区域

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

1
2
3
4
X X X X
X O O X
X X O X
X O X X

运行你的函数后，矩阵变为：

1
2
3
4
X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

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
class Solution {
    private boolean[][] juge = new boolean[1000][1000];
    public void solve(char[][] board) {
    if (board.length - 1 <= 0 || board[0].length <= 0) return;
    int m = board.length - 1;
    int n = board[0].length - 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (board[i][j] == 'O' && !juge[i][j])
                bfs(i, j, board, m, n);
        }
    }

}

public void bfs(int x, int y, char[][] board, int m, int n) {
    List<int[]> jugehuan = new ArrayList<>();
    boolean isHuan = false;
    //能改变的方向四个
    int[][] change = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    //bfs队列
    Queue<int[]> q = new LinkedList<>();
    int[] one = {x, y};
    //扫描到的第一个0进入队列
    q.add(one);
    board[x][y] = 'X';
    juge[x][y] = true;
    while (!q.isEmpty()) {
        int[] nowxy = q.poll();
        jugehuan.add(nowxy);
        for (int i = 0; i < 4; i++) {
            int changex = nowxy[0] + change[i][0];
            int changey = nowxy[1] + change[i][1];
            if (changex >= 1 && changex < m && changey >= 1 && changey < n) {
                if (board[changex][changey] == 'O') {
                    int[] now = {changex, changey};
                    q.add(now);
                    board[changex][changey] = 'X';
                    juge[changex][changey] = true;
                }
            } else {
                if (board[changex][changey] == 'O')
                    isHuan = true;
            }
        }
    }
    if (isHuan) {
        for (int i = 0; i < jugehuan.size(); i++) {
            board[jugehuan.get(i)[0]][jugehuan.get(i)[1]] = 'O';
        }
    }
}
}