题目链接

Leetcode.130 被围绕的区域 mid

题目描述

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

示例 1：

输入：board = [[“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’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [[“X”]]
输出：[[“X”]]

提示：

• $m==board.length$
• $n==board[i].length$
• $1<=m,n<=200$
• board[i][j]为 'X'或 'O'

解法：dfs

我们先从 $board$ 的四周，与边界相邻的 $board[i][j]=$ ’O'的区域记录下来，这些区域是不能被 'X'填充的。

接着，剩下的 $board[i][j]=$ ’O'的区域才是能被 'X'填充的。

时间复杂度： $O(mn)$

C++代码：

class Solution {
public:
    void solve(vector<vector<char>>& g) {
        int m = g.size() , n = g[0].size();
        //记录是否被访问过
        bool vis[m][n];
        memset(vis,false,sizeof vis);

        function<void(int ,int,bool)> dfs = [&](int i,int j,bool mode) -> void{
            if(i < 0 || i >= m || j < 0 || j >= n || vis[i][j]) return;
            if(g[i][j] == 'X') return;
            
            vis[i][j] = true;
            if(mode) g[i][j] = 'X';

            dfs(i + 1,j,mode);
            dfs(i - 1,j,mode);
            dfs(i,j + 1,mode);
            dfs(i,j - 1,mode);
        };
        //记录从左右两边开始的 不能被 'X' 填充的位置
        for(int i = 0;i < m;i++){
            if(g[i][0] == 'O' && !vis[i][0]) dfs(i,0,false);
            if(g[i][n-1] == 'O' && !vis[i][n-1]) dfs(i,n-1,false);
        }
        //记录从上下两边开始的 不能被 'X' 填充的位置
        for(int j = 0;j < n;j++){
            if(g[0][j] == 'O' && !vis[0][j]) dfs(0,j,false);
            if(g[m-1][j] == 'O' && !vis[m-1][j]) dfs(m-1,j,false);
        }
        //剩下的 g[i][j] == 'O' 并且没有被访问过的位置 都可以被 'X'填充
        for(int i = 1;i < m - 1;i++){
            for(int j = 1;j < n - 1;j++){
                if(g[i][j] == 'O' && !vis[i][j]) dfs(i,j,true);
            }
        }
    }
};