题解: 使用并查集解决 AC代码(c++)
class Solution {
public:
int father[100005];
int pos[1005][1005];
void solve(vector<vector<char>>& board) {
memset(tag,0,sizeof(tag));
for(int i=0;i<=100000;i++)
father[i]=i;
int p = 0;
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[i].size();j++)
{
if(board[i][j]=='O')
{
pos[i][j] = ++p;
if(i==board.size()-1||j==board[i].size()-1||i==0||j==0)
{
father[p] = 0;
}
}
}
}
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[i].size();j++)
{
if(board[i][j]=='O')
{
if(j-1>=0&&board[i][j-1] == 'O')
{
join(i,j,i,j-1);
}
if(i-1>=0&&board[i-1][j]=='O')
{
join(i,j,i-1,j);
}
}
}
}
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[i].size();j++)
{
if(board[i][j]=='O')
{
find(pos[i][j]);
if(father[pos[i][j]]!=0)
board[i][j] = 'X';
}
}
}
}
void join(int i1,int j1,int i2,int j2)
{
int f1 = find(pos[i1][j1]);
int f2 = find(pos[i2][j2]);
if(f1!=f2)
{
if(f1==0) father[f2] = f1;
else if(f2==0) father[f1] = f2;
else father[f2] =f1;
}
}
int find(int x)
{
if(x!=father[x])
father[x] = find(father[x]);
return father[x];
}
};