【算法积累】被围绕的区域

骑猪看日落 2022-12-27 07:17 165阅读 0赞

## LeetCode 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'`都不会被填充为`'X'`。不难发现，所有的不被包围的`'O'`都直接或间接与边界上的`'O'`相连。对于每一个边界上的`'O'`，以其为起点，利用深度优先搜索的方法，将所有与其直接或间接相连的字母`'O'`标记为特殊符号`'#'`。搜索结束后，遍历给定的二维矩阵，如果字母为`'O'`，则将其改写为`'X'`；如果字母被标记为`'#'`，则将其还原为`'O'`。  
语言：C

void dfs(char** board, int i, int j, int row, int col) { 
        if (i >= row || i < 0 || j >= col || j < 0 || board[i][j] != 'O') { 
            return;
        }
        board[i][j] = '#';
        dfs(board, i - 1, j, row, col);
        dfs(board, i + 1, j, row, col);
        dfs(board, i, j - 1, row, col);
        dfs(board, i, j + 1, row, col);
    }
    
    void solve(char** board, int boardSize, int* boardColSize) { 
        if (boardSize == 0) { 
            return;
        }
        int row = boardSize;
        int col = boardColSize[0];
        // 沿行遍历边界
        for (int i = 0; i < col; i++) { 
            if (board[0][i] == 'O') { 
                dfs(board, 0, i, row, col);
            }
            if (board[row - 1][i] == 'O') { 
                dfs(board, row - 1, i, row, col);
            }
        }
        // 沿列遍历边界
        for (int i = 0; i < row; i++) { 
            if (board[i][0] == 'O') { 
                dfs(board, i, 0, row, col);
            }
            if (board[i][col - 1] == 'O') { 
                dfs(board, i, col - 1, row, col);
            }
        }
        // 改写矩阵
        for (int i = 0; i < row; i++) { 
            for (int j = 0; j < col; j++) { 
                if (board[i][j] == 'O') { 
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') { 
                    board[i][j] = 'O';
                }
            }
        }
    }

时间复杂度： O ( n × m ) O(n\\times m) O(n×m)，其中 n n n和 m m m分别为二维矩阵的行数和列数。  
空间复杂度： O ( n × m ) O(n\\times m) O(n×m)，其中 n n n和 m m m分别为二维矩阵的行数和列数，主要为深度优先搜索的栈的开销。

> 这道题还可以使用广度优先搜索（BFS）或者并查集来解决，不过这周的事情有一些多，先写一个较为简单的DFS的解法，后面有时间了再把BFS和并查集的解法补上。