【Leetcode】130.被围绕的区域

130 被围绕的区域

题目

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

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

示例:
X X X X
X O O X
X X O X
X O X X

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

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

方法(DFS)

据题意，我们需要将矩阵中的中的’O’分为以下两种：

  • 边界上的’O’和与边界上相邻的’O’
  • 被’X’围绕的’O’

对于后者，我们需要将其改为’X’。而前者则无需改动。

先写一个深度优先遍历的函数，暂且叫它感染函数。它能实现将所有与当前位置相连的’O’修改成’#’。
所以第一步，我们先处理矩阵的四个边界，若在遍历边界的时候遇到’O’,则进入感染过程，将与边界上的’O’相连的’O’全都改写成’#’，以将上述两种’O’区别开来。

第二步，我们遍历整个矩阵，若遇到’O’，则这个’O’是被围绕的’O’，于是将其改为’X’。若遇到’#’，则代表其是边界上的’O’，于是将其改为’O’。

代码

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
public void solve(char[][] board) {
    if(board == null || board.length == 0)
        return;
    //第一步：处理边界
    int rows = board.length;
    int cols = board[0].length;
    for(int j = 0; j < cols ; j++){
        if(board[0][j] == 'O')
            infect(board, 0, j);
    }
    for(int j = 0; j < cols ; j++){
        if(board[rows - 1][j] == 'O')
            infect(board, rows - 1, j);
    }
    for(int i = 0; i < rows ; i++){
        if(board[i][0] == 'O')
            infect(board, i, 0);
    }
    for(int i = 0; i < rows; i++){
        if(board[i][cols - 1] == 'O')
            infect(board, i, cols - 1);
    }
    //第二步：遍历矩阵
    for(int i = 0; i < board.length; i++){
        for(int j = 0; j < board[0].length; j++){
            if(board[i][j] == 'O')
                board[i][j] = 'X';
            if(board[i][j] == '#')
                board[i][j] = 'O';
        }
    }
}

public void infect(char[][] board, int i, int j){
    if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#')
        return;
    board[i][j] = '#';
    infect(board, i - 1, j);
    infect(board, i + 1, j);
    infect(board, i, j - 1);
    infect(board, i, j + 1);
}