题目描述

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

样例

使用dfs,bfs,并查集求解

算法1

(暴力枚举) $O(？)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
     vector<vector<int>> isConnectBoard;
     void setConnectBoard(vector<vector<char>> board,int i,int j)
     {   
         int m = board.size();
         int n = board[0].size();
         if(board[i][j]!='O') return;
         int dx[4]={1,-1,0,0};
         int dy[4]={0,0,1,-1};
         for(int k=0;k<4;k++)
         {
             int a = i+dx[k];
             int b = j+dy[k];
             if(a>=0 && b>=0 && a<m &&b<n && isConnectBoard[a][b]==1) 
             {
                 isConnectBoard[i][j]=1;
                 break;
             }
         }
         if(isConnectBoard[i][j]==1)
         {
             //遍历当前O周围的所有O
             for(int k=1;k<4;k++)
             {
                 int a = i+dx[k];
                 int b = j+dy[k];
                 //对于已经判断为与边界联通的点，其周围一定已经遍历过了
                 if(a>=0 && b>=0 && a<m &&b<n && isConnectBoard[a][b]!=1) setConnectBoard(board,a,b);
             }
         }

     }

    void solve(vector<vector<char>>& board) {
    //暴力超时
         int m = board.size();
         int n = board[0].size();
         //初始化isConnectBoard（只考虑边界）
         for(int i=0;i<m;i++)
         {
             vector<int> cols;
             for(int j=0;j<n;j++) 
             {
                 if(board[i][j]=='O' && (i==0 || j==0 || i==m-1 || j==n-1)) cols.push_back(1);
                 else cols.push_back(0);
             }
             isConnectBoard.push_back(cols);
         }

         int dx[4]={1,-1,0,0};
         int dy[4]={0,0,1,-1};
         for(int i=0;i<m;i++)
             for(int j=0;j<n;j++) setConnectBoard(board,i,j);
         for(int i=0;i<m;i++)
         {
             for(int j=0;j<n;j++)
             {
                 if(board[i][j]=='O' && isConnectBoard[i][j]==0) board[i][j]='X';
             }
         }
    }
};

算法2

(深度遍历优先)

树遍历解法：以矩阵的边界上的点为根节点出发，与其连通的’O’被标记为’A’，最终未被标记的点赋值为’X’,’A’转回’O’

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

参考文献

C++ 代码

class Solution {
public:
     //1.深度优先搜索
     void dfs(vector<vector<char>>& board,int i,int j)
     {
         int m = board.size();
         int n = board[0].size();
         if(i<0 || j<0 || i>=m ||j>=n || board[i][j]!='O') return;
         board[i][j] ='A';
         int dx[4]={1,-1,0,0};
         int dy[4]={0,0,1,-1};
         for(int k=0;k<4;k++)
         {
             int a = i+dx[k];
             int b = j+dy[k];
             dfs(board,a,b);
         }
     }
    void solve(vector<vector<char>>& board) {

    //树遍历解法：以矩阵的边界上的点为根节点出发，与其连通的'O'被标记为'A'，最终未被标记的点赋值为'X','A'转回'O'   
         int m = board.size();
         int n = board[0].size();
         //2.广度优先搜索
         queue<pair<int,int>> q; 
         for(int i=0;i<m;i++)
         {
             dfs(board,i,0);
             dfs(board,i,n-1);
         }
         for(int i=1;i<n-1;i++)
         {
             dfs(board,0,i);
             dfs(board,m-1,i);

         }
         for(int i=0;i<m;i++)
             for(int j=0;j<n;j++)
             {
                 if(board[i][j]=='A') board[i][j]='O';
                 else if(board[i][j]=='O') board[i][j]='X';
             }
    }
};

算法3

(广度遍历优先)

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

参考文献

C++ 代码

class Solution {
public:
    void solve(vector<vector<char>>& board) {
    //树遍历解法：以矩阵的边界上的点为根节点出发，与其连通的'O'被标记为'A'，最终未被标记的点赋值为'X','A'转回'O'   
         int m = board.size();
         int n = board[0].size();
         //2.广度优先搜索
         queue<pair<int,int>> q; 
         for(int i=0;i<m;i++)
         {

             if(board[i][0]=='O') q.push({i,0});
             if(board[i][n-1]=='O') q.push({i,n-1});
         }
         for(int i=1;i<n-1;i++)
         {

             if(board[0][i]=='O') q.push({0,i});
             if(board[m-1][i]=='O') q.push({m-1,i});
         }

         int dx[4]={1,-1,0,0};
         int dy[4]={0,0,1,-1};
         while(q.size()>0)
         {
             auto t = q.front();
             board[t.first][t.second] = 'A';
             q.pop();
             for(int k=0;k<4;k++)
             {
                 int a = t.first +dx[k];
                 int b = t.second +dy[k];
                 if(a>=0 && b>=0 && a<m && b<n && board[a][b]=='O') q.push({a,b});
             }
         }
         for(int i=0;i<m;i++)
             for(int j=0;j<n;j++)
             {
                 if(board[i][j]=='A') board[i][j]='O';
                 else if(board[i][j]=='O') board[i][j]='X';
             }
    }   
};

算法4

(并查集)

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

参考文献

C++ 代码

class UF{
private:
    int *parent;
    int *size;
    int count;
public:
    UF(int n)
    {//构造，n个节点互不连通
        parent = new int[n];
        size = new int[n];
        count = n;
        for(int i=0;i<n;i++)
        {
            //并查集初始化，自己是自己的父亲
            parent[i] = i;
            size[i] = i;
        }
    }
    int find(int x)
    {
        if(x!=parent[x])
        {
            parent[x] = parent[parent[x]];
            x =parent[x];
        }
        return x;
    }
    void myunion(int i,int j)
    {
        int a = find(i);
        int b = find(j);
        if(a==b) return;
        if(size[a]<size[b])
        {
            parent[a] = b;
            size[b] +=size[a];          
        }
        else{
            parent[b] = a;
            size[a] +=size[b];
        }
        count--;
    }
    bool connect(int i,int j)
    {
        int a = find(i);
        int b = find(j);
        if(a==b) return true;
        else return false;
    }
};

class Solution {
public:
    void solve(vector<vector<char>>& board) {
    //并查集法:超时
            int m = board.size();
            int n = board[0].size();
            //+1：是为了给在边界或与边界连通的节点的父节点申请一个位置
            UF *uf = new UF(m*n+1);
            for(int i=0;i<m;i++)
            {
                //二维坐标转一维映射
                if(board[i][0]=='O') uf->myunion(m*n,i*n);
                if(board[i][n-1]=='O') uf->myunion(m*n,i*n+n-1);
            }
            for(int i=1;i<n-1;i++)
            {
                if(board[0][i]=='O') uf->myunion(m*n,i);
                if(board[m-1][i]=='O') uf->myunion(m*n,(m-1)*n+i);
            }
            int dx[4]={1,-1,0,0};
            int dy[4]={0,0,1,-1};
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++)
                {
                    if(board[i][j]=='O')
                    {
                        for(int k=0;k<4;k++)
                        {
                            int a = i+dx[k];
                            int b = j+dy[k];
                            if(a>=0&&b>=0&&a<m&&b<n&&board[a][b]=='O') uf->myunion(i*n+j,a*n+b);
                        }
                    }
                }
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++)
                {
                    if(!uf->connect(i*n+j,m*n)) board[i][j] = 'X';
                }
    }   
};