echo

任生命穿梭 时间的角落

0%

被围绕的区域

Posted on In Valine:

130. 被围绕的区域

给定一个二维的矩阵，包含 '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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

自己的想法：从每一个字母O（不在边界上）开始DFS，遇到四个 X 返回，在返回过程中将 O 修改为 X；如果碰到边界，直接返回。

发现返回的条件太复杂，不会实现。

下面是官方题解：

给定矩阵中有三种元素：

  • 字母X
  • 被字母 X 包围的字母 O
  • 没有被字母 X 包围的字母 O

要判断字母 O 是否被字母 X 包围比较困难，注意到：任何边界上的 O 都不会被填充为X。我们可以想到，所有不被 X 包围的 O 都与边界上的 O 相连。我们利用这个性质判断 O 是否被 X 包围：

  • 对于每个边界上的 O，我们以它为起点，标记所有与之相连或间接相连的字母 O
  • 遍历这个矩阵，对于每个字母：
    • 如果该字母被标记过，则表示它没有被字母X包围，将其恢复为 O
    • 如果该字母没有被标记，则表示它被字母 X 包围，将其改为 X

方法一：DFS

使用深度优先搜索实现标记，我们将标记过的字母 O 改为 字母A。

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
class Solution {
    private int m, n;
    public void solve(char[][] board) {
        m = board.length;
        if(m == 0){
            return;
        }
        n = board[0].length;
		//标记与边界相连的字母 O
        for(int i = 0; i < m; i++){
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
		//标记与边界相连的字母 O
        for(int i = 1; i < n - 1; i++){
            dfs(board, 0, i);
            dfs(board, m - 1, i);
        }
		//处理每一个字母
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; 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 x, int y){
        if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O'){
            return;
        }
		//标记与边界相连的字母 O
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
}

时间复杂度O(mn)，空间复杂度O(mn)。m，n为矩阵的长宽。

方法二：BFS

我们使用广度优先搜索来实现标记，同样，将标记过的字母 O 改为 字母A。

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
class Solution {
    int[] dx = new int[]{1, -1, 0, 0};
    int[] dy = new int[]{0, 0, 1, -1};

    public void solve(char[][] board) {
        int m = board.length;
        if(m == 0){
            return;
        }
        int n = board[0].length;
        Queue<int[]> queue = new LinkedList<>();
		//将边界上的字母 O 坐标加入队列
        for(int i = 0; i < m; i++){
            if(board[i][0] == 'O') queue.offer(new int[]{i, 0});
            if(board[i][n - 1] == 'O') queue.offer(new int[]{i, n - 1});
        }

        for(int i = 1; i < n - 1; i++){
            if(board[0][i] == 'O') queue.offer(new int[]{0, i});
            if(board[m - 1][i] == 'O')queue.offer(new int[]{m - 1, i});
        }
		//将边界上的字母 O 坐标加入队列
        while(!queue.isEmpty()){
            //从队列中取出一个字母 O，对其标记
            int[] t = queue.poll();
            int x = t[0], y = t[1];
            board[x][y] = 'A';
			//将当前字母 O 相连的字母 O 坐标加入队列
            for(int i = 0; i < 4; i++){
                int nx = x + dx[i], ny = y + dy[i];
                if(nx < 0 || nx >= m || ny < 0 || ny >= n || board[nx][ny] != 'O'){
                    continue;
                }
                queue.offer(new int[]{nx, ny});
            }
        }
		//处理每一个字母
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == 'A'){
                    board[i][j] = 'O';
                }else if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
    }
}

时间复杂度O(mn)，空间复杂度O(mn)。m，n为矩阵的长宽。