130

130.go

type unionFind struct {
    parent []int
    rank []int
    boundedNode map[int] bool
}

func NewUnionFind(board [][]byte) *unionFind {
    m := len(board)
    n := len(board[0])
    
    parent := make([]int, m * n)
    rank := make([]int, m * n)
    boundedNode := make(map[int] bool, m * n)
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == byte('O') {
                parent[i * n + j] = i * n + j
            }
            rank[i * n + j] = 0
        }
    }
    
    return &unionFind{parent, rank, boundedNode}
}

func (uf *unionFind) find(x int) int {
    if x != uf.parent[x] {
        uf.parent[x] = uf.find(uf.parent[x])
    }
    
    return uf.parent[x]
}

func (uf *unionFind) union(x, y int) {
    rootX := uf.find(x)
    rootY := uf.find(y)
    
    if rootX == rootY {
        return
    }
    
    if uf.rank[rootX] < uf.rank[rootY] {
        uf.parent[rootX] = rootY
    } else if uf.rank[rootX] > uf.rank[rootY] {
        uf.parent[rootY] = rootX
    } else {
        uf.parent[rootY] = rootX
        uf.rank[rootX]++
    }
}

func solve(board [][]byte)  {
    if board == nil || len(board) == 0 {
        return
    }
    
    uf := NewUnionFind(board)
    
    m := len(board)
    n := len(board[0])
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 'O' {
                if i - 1 >= 0 && board[i - 1][j] == byte('O') {
                    uf.union(i * n + j, (i - 1) * n + j)
                }
                if i + 1 < m && board[i + 1][j] == byte('O') {
                    uf.union(i * n + j, (i + 1) * n + j)
                }
                if j - 1 >= 0 && board[i][j - 1] == byte('O') {
                    uf.union(i * n + j, i * n + (j - 1))
                }
                if j + 1 < n && board[i][j + 1] == byte('O') {
                    uf.union(i * n + j, i * n + (j + 1))
                }
                
                if i == 0 || i == m - 1 || j == 0 || j == n - 1 {
                    uf.boundedNode[uf.find(i * n + j)] = true
                }
            }
        }
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == byte('O') && uf.boundedNode[uf.find(i * n + j)] == false  {
                board[i][j] = byte('X')
            }
        }
    }
}