LeetCode-130. 被围绕的区域-广度优先和深度优先

题目描述

给你一个 m x n 的矩阵 board ，由若干字符 X 和 O ，找到所有被 X 围绕的区域，并将这些区域里所有的 O用 X 填充。

注意边界上的O不会被包围，也就是边界上的O不会被填充成为X

解题思路

board 矩阵中具有三种元素，字符X，被X包围的字符O，没有被X包围的字符O

由于边界上的O不会被填充为X，所以可以转换思想为所有不被X包围的O都与边界的O直接或者间接的相连。

访问四边的边界开始，边界的O就是起点，将O和直接或者间接相连的O标记起来。

标记设定为字符 A，数组标记完毕之后，遍历数组，被标记的就是O没有被标记的就是X

深度优先算法

DFS，从边界开始遍历递归遍历数组进行标记，这里在标记左右和上下两组边的时候，去掉重叠的部分，dfs中判断直接或者间接与边界O相邻的情况就标记为A，这样标记结束之后，数组就剩下标记的A和未标记的O以及原来的X，未标记的O就是被包围的，将其更新为X，标记的A就是未被包围的字符，将其更新为O

dfs 控制边界一旦越界就结束

class Solution {
    int row,col;
    public void solve(char[][] board) {
        row = board.length;
        if(row == 0) return;
        col = board[0].length;
        
        // 初始化board左右两个边,0和col-1列
        for(int i = 0; i < row; i++){
            dfs(board,i,0);
            dfs(board,i,col - 1);
        }
        // 初始化board上下两个边，不包含重叠的部分
        for(int j = 1; j < col-1; j++){
            dfs(board,0,j);
            dfs(board,row-1,j);
        }

        // 根据标记还原数组
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(board[i][j] == 'A'){
                    board[i][j] = 'O';
                }else if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
    }
    public void dfs(char[][] board,int i,int j){
        if(i < 0 || i >= row || j < 0 || j >= col || board[i][j] != 'O'){
            return;
        }
        // 直接或者间接与边界O相连
        board[i][j] = 'A';
        dfs(board,i+1,j);
        dfs(board,i-1,j);
        dfs(board,i,j+1);
        dfs(board,i,j-1);
    }
}
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

广度优先算法

左边和右边的初始化，遇到O入队并且标记

初始化了方向数组，遍历一次对应上下左右的直接相邻。使用了队列保存边界O的联通元素的索引，队列具有O的连通分量就是入队，将该位置标记为A

最后将标记的位置的元素还原即可

class Solution {
    public void solve(char[][] board) {
        int row = board.length;
        if(row == 0) return;
        int col = board[0].length;
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        Deque<int[]> queue = new LinkedList<>();

        // 初始化并且标记四个边
        for(int i = 0; i < row; i++){
            if(board[i][0] == 'O'){
                queue.offer(new int[]{i, 0});
                board[i][0] = 'A';
            }
            if(board[i][col-1] == 'O'){
                queue.offer(new int[]{i, col-1});
                board[i][col-1] = 'A';
            }
        }
        for(int i = 1; i < col-1; i++){
            if(board[0][i] == 'O'){
                queue.offer(new int[]{0, i});
                board[0][i] = 'A';
            }
            if(board[row-1][i] == 'O'){
                queue.offer(new int[]{row-1, i});
                board[row-1][i] = 'A';
            }
        }

        while(!queue.isEmpty()){
            int[] e = queue.poll();
            int x = e[0],y = e[1];
            for(int i = 0; i < 4; i++){
                int mx = x + dx[i],my = y + dy[i];
                if(mx < 0 || mx >= row || my < 0 || my >= col || board[mx][my] != 'O'){
                    continue;
                }
                queue.offer(new int[]{mx,my});
                board[mx][my] = 'A';
            }
        }
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(board[i][j] == 'A'){
                    board[i][j] = 'O';
                }else if(board[i][j] == 'O'){
                    board[i][j] = '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
54
55