欢迎访问LeetCode题解合集

题目描述

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

题解：

这题本质是 连通块 。

找到所有被包围的 O 不好处理，那么反过来思考，先确定那些不会被包围的 O ，那么剩下的就是会被包围的 O 了。

怎么确定不会被包围的 O 呢，边界上的肯定不会被包围，与边界上的 O 属于同一个 联通块 的 O 也不会被包围，所以就是查找与边界上的 o 相连的联通块。

深搜、广搜、并查集都可以，这里只提供 深搜 版本。

时间复杂度：$O(n * m)$

额外空间复杂度：$O(n * m)$

class Solution {
public:
    vector<int> dx, dy;
    void dfs(vector<vector<char>>& board, int x, int y ) {
        board[x][y] = '#';
        for ( int k = 0; k < 4; ++k ) {
            int tx = x + dx[k];
            int ty = y + dy[k];
            if ( tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size() || board[tx][ty] != 'O' ) continue;
            dfs( board, tx, ty );
        }
    }
    void solve(vector<vector<char>>& board) {
        int n = board.size();
        if ( n < 3 ) return;
        int m = board[0].size();
        if ( m < 3 ) return;
        dx = vector<int>{ -1, 0, 1, 0 };
        dy = vector<int>{ 0, 1, 0, -1 };
        for ( int i = 0; i < m; ++i ) {
            if ( board[0][i] == 'O' ) dfs( board, 0, i );
            if ( board[n - 1][i] == 'O' ) dfs( board, n - 1, i );
        }
        for ( int i = 1; i < n - 1; ++i ) {
            if ( board[i][0] == 'O' ) dfs( board, i, 0 );
            if ( board[i][m - 1] == 'O' ) dfs( board, i, m - 1 );
        }
        for ( int i = 0; i < n; ++i ) {
            for ( int j = 0; j < m; ++j ) {
                if ( board[i][j] == 'X' ) continue;
                if ( board[i][j] == 'O' ) board[i][j] = 'X';
                else board[i][j] = 'O';
            }
        }
    }
};
/*
时间：12ms，击败：95.79%
内存：9.6MB，击败：94.45%
*/