LeetCode 130 주변 지역 (집합)

Given a 2D board containing  'X'  and  'O'  (the letter O), capture all regions surrounded by  'X' .
A region is captured by flipping all  'O' s into  'X' s in that surrounded region.
For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

제목: 'O' 와 'X' 만 포 함 된 2 차원 문자 배열 을 보 여 주 며 'X' 에 둘러싸 인 'O' 를 'X' 로 바 꿉 니 다.
문제 풀이 방향: 'X' 에 둘러싸 이지 않 은 'O' 를 같은 집합 에 넣 고 배열 을 옮 겨 다 니 며 집합 에 없 는 'O' 를 'X' 로 변환 합 니 다.
코드 는 다음 과 같 습 니 다:

#define MAXN 100005
typedef struct DisjointSet{
    int par,rank;
}DS;
DS ds[MAXN];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

void init(int n)
{
    for(int i = 0;i <= n;i++){
        ds[i].par = i;
        ds[i].rank = 0;
    }
}

int find(int x)
{
    if(x == ds[x].par)
        return x;
    else return ds[x].par = find(ds[x].par);
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return ;
    if(ds[x].rank < ds[y].rank)
        ds[x].par = y;
    else {
        if(ds[x].rank == ds[y].rank)
            ds[x].rank++;
        ds[y].par = x;
    }
    return ;
}

int same(int x, int y)
{
    return find(x) == find(y);
}

void solve(char** board, int boardRowSize, int boardColSize) {
    int brs = boardRowSize;
    int bcs = boardColSize;
    init(bcs * brs);
    for(int i = 0;i < brs;i++){
        for(int j = 0;j < bcs;j++){
            if((i == 0 || i == brs-1 || j == 0 || j == bcs-1) && board[i][j] == 'O')
                unite(i*brs+j, brs*bcs);
            else if(board[i][j] == 'O'){
                for(int k = 0;k < 4;k++){
                    int x = i + dir[k][0];
                    int y = j + dir[k][1];
                    if(board[x][y] == 'O')
                        unite(i*brs+j, x*brs+y);
                }
            }
        }
    }
    for(int i = 0;i < brs;i++){
        for(int j = 0;j < bcs;j++){
            if(!same(i*brs+j, brs*bcs)) board[i][j] = 'X';
        }
    }
    return ;
}