首页 > 其他分享 >130. 被围绕的区域

130. 被围绕的区域

时间:2022-09-07 00:58:27浏览次数:73  
标签:tu 区域 int 围绕 vis 130 board minu minv

130. 被围绕的区域

给你一个 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'

解析:

求连通区域的行列的最值即可

class Solution {
public:

    vector<pair<int, int> > rute;
    int n, m;
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    bool vis[210][210];
    void dfs(vector<vector<char> > &board, int u, int v, int& maxu, int& maxv, int &minu, int &minv)
    {
        vis[u][v] = 1;
        maxu = max(maxu, u);
        maxv = max(maxv, v);
        minu = min(minu, u);
        minv = min(minv, v);
        rute.push_back(pair<int, int> (u, v));
        for(int i = 0; i < 4; i++)
        {
            int tu = u + dir[i][0];
            int tv = v + dir[i][1];
            if(tu < 0 || tv < 0 || tu >= n || tv >= m || board[tu][tv] == 'X' || vis[tu][tv]) continue;
            vis[tu][tv] = 1;
            dfs(board, tu, tv, maxu, maxv, minu, minv);
        }
    }


    void solve(vector<vector<char>>& board) {
        n = board.size();
        m = board[0].size();
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(board[i][j] == 'O' && vis[i][j] == 0)
                {
                    vis[i][j] = 1;
                    rute.clear();
                    int maxu = i, maxv = j, minu = i, minv = j;
                    dfs(board, i, j, maxu, maxv, minu, minv);
                    if(maxu < n - 1 && maxv < m - 1 && minu > 0 && minv > 0)
                    {
                        for(int k = 0; k < rute.size(); k++)
                            board[rute[k].first][rute[k].second] = 'X';
                    }
                }


            }


        }




    }
};

 

标签:tu,区域,int,围绕,vis,130,board,minu,minv
From: https://www.cnblogs.com/WTSRUVF/p/16663861.html

相关文章