题目
给你一个 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"]]
解题
方法一：dfs
转化为从边缘的O开始dfs，对其进行标记。那么没有标记的O就是需要转化为X的
class Solution { public: int m,n; void dfs(vector<vector<char>>& board,int x,int y){ if(x<0||x>=m||y<0||y>=n||board[x][y]!='O') return; board[x][y]='#'; dfs(board,x+1,y); dfs(board,x-1,y); dfs(board,x,y-1); dfs(board,x,y+1); } void solve(vector<vector<char>>& board) { m=board.size(),n=board[0].size(); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]=='O'&&(i==0||i==m-1||j==0||j==n-1)){ dfs(board,i,j); } } } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]=='O') board[i][j]='X'; else if(board[i][j]=='#') board[i][j]='O'; } } } };
方法二：并查集
将边界的O都和dummy连接起来，其他的O与4个方向的O连接起来。
最后只要将不与dummy连接的O转为X即可
class UnionFind{ private: vector<int> parent; public: UnionFind(int m){ parent.resize(m); iota(parent.begin(),parent.end(),0); } int find(int index){ if(index==parent[index]) return index; return parent[index]=find(parent[index]); } void unite(int index1,int index2){ parent[find(index1)]=find(index2); } bool isConnect(int index1,int index2){ return find(index1)==find(index2); } }; class Solution { private: int m,n; int node(int i,int j){ return i*n+j; } public: void solve(vector<vector<char>>& board) { m=board.size(),n=board[0].size(); UnionFind uf(m*n+1); int dummyIndex=m*n; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]=='X') continue; if(i==0||j==0||i==m-1||j==n-1){ uf.unite(node(i,j),dummyIndex); }else{ if(i>0&&board[i-1][j]=='O'){ uf.unite(node(i,j),node(i-1,j)); } if(i<m-1&&board[i+1][j]=='O'){ uf.unite(node(i,j),node(i+1,j)); } if(j>0&&board[i][j-1]=='O'){ uf.unite(node(i,j),node(i,j-1)); } if(j<n-1&&board[i][j+1]=='O'){ uf.unite(node(i,j),node(i,j+1)); } } } } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(uf.isConnect(node(i,j),dummyIndex)){ board[i][j]='O'; }else{ board[i][j]='X'; } } } } };
