LeetCode 130. 被围绕的区域(并查集)
原题链接
简单
作者:
orange0912
,
2021-12-30 10:05:31
,
所有人可见
,
阅读 227
本题dfs改并查集,设置虚拟节点编号为nm,然后将边缘的节点及其与边缘能连接上的节点都纳入nm的节点下,最后遍历所有棋盘上的O点,如果从O点开始4个方向的点也是O点,同时也是nm编号的集合内的点,则纳入到集合nm下
最后棋盘上的O点再遍历一次,如果O点和虚拟节点不在同一个并查集,则将O可以置为X
class Solution {
public:
vector<int> p;
int n,m;
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
void merge(int a,int b)
{
int pa=find(a);
int pb=find(b);
if(pa!=pb)
p[pa]=pb;
}
void solve(vector<vector<char>>& board) {
n=board.size();
m=board[0].size();
p.assign(n*m+10,0);
for(int i=0;i<=n*m;i++) p[i]=i;
//第0列和第m-1列的合并
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(board[i][j]=='O'&& (i==0||i==n-1||j==0||j==m-1) )
{
int k=i*m+j;
merge(k,n*m);
}
}
}
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
for(int i=1;i<n-1;i++)
{
for(int j=1;j<m-1;j++)
{
if(board[i][j]=='O')
{
int kt=i*m+j;
for(int k=0;k<4;k++) //搜寻四个方向
{
int kx=i+dx[k];
int ky=j+dy[k];
int kk=kx*m+ky;
if(board[kx][ky]=='O')//新方向上是O则表示可以和边缘合并为并查集
merge(kt,kk);
}
}
}
}
//遍历并查集,最后若中间一块的节点上和dumpy虚拟节点未在同一个并查集,则表示周围都是被围住了,可以转为X
int d=n*m;
int pd=find(d);
for(int i=1;i<n-1;i++)
{
for(int j=1;j<m-1;j++)
{
int kd=i*m+j;
int pk=find(kd);
if(pd!=pk) //不在同一个并查集
board[i][j]='X';
}
}
}
};