LeetCode 130 被围绕的区域
1、题目
给定一个二维的矩阵,包含 ‘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’。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
2、分析
采用:并查集
四周边缘的’O’看成第一类,中间不和’O’联通的’O’看成第二类。题目意思即是把第二类的’O’变成’X’。采用并查集,找到同一类就合并。由于一维数组更方便找父节点,所以把二维数组映射为一维数组。即nm行的数组映射为下标0~nm-1,而我们的并查集集合开一个nm+1的数组,下标nm为一个虚节点,把第一类的节点归为虚节点一类,这样在最后遍历时,只需要判断是否和虚节点为一类,则可以知道是否需要变为’X’。
3、代码
class Solution {
public:
vector<int> p;
int find(int x)
{
if(p[x]!=x)
{
p[x]=find(p[x]); //一定要路径压缩一下,不然会超时
return find(p[x]);
}
return p[x];
}
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
void solve(vector<vector<char>>& board) {
if(board.empty()||board[0].empty()) return;
int n=board.size(),m=board[0].size();
for(int i=0;i<=n*m;i++) p.push_back(i); //m*n是虚节点
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(board[i][j]=='O')
{
if(i==0||i==n-1||j==0||j==m-1) //若是在四周边缘处,和虚节点合并
p[find(i*m+j)]=find(n*m);
else
{
for(int k=0;k<4;k++) //向四个方向合并
{
int nexi=i+dx[k],nexj=j+dy[k];
if(nexi>=0&&nexi<n&&nexj>=0&&nexj<m)
{
if(board[nexi][nexj]=='O')
p[find(i*m+j)]=find(nexi*m+nexj);
}
}
}
}
}
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(board[i][j]=='O')
{
if(find(i*m+j)==find(m*n)) continue; //判断是否和虚节点是一类
else board[i][j]='X';
}
}
}
};