Thanks for this unoin find way and I rewrite in python:

class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board:
return
m = len(board)
n = len(board[0])
uf = UnionFind(m * n + 1)
dummyNode = m * n
for j in range(n):
if board[0][j] == 'O':
uf.union(self.node(0, j, n), dummyNode)
if board[m - 1][j] == 'O':
uf.union(self.node(m - 1, j, n), dummyNode)
for i in range(m):
if board[i][0] == 'O':
uf.union(self.node(i, 0, n), dummyNode)
if board[i][n - 1] == 'O':
uf.union(self.node(i, n - 1, n), dummyNode)
for i in range(1, m - 1):
for j in range(1, n - 1):
if board[i][j] != 'O':
continue
if board[i - 1][j] == 'O':
uf.union(self.node(i - 1, j, n), self.node(i, j, n))
if board[i + 1][j] == 'O':
uf.union(self.node(i + 1, j, n), self.node(i, j, n))
if board[i][j - 1] == 'O':
uf.union(self.node(i, j - 1, n), self.node(i, j, n))
if board[i][j + 1] == 'O':
uf.union(self.node(i, j + 1, n), self.node(i, j, n))
for i in range(m):
for j in range(n):
if uf.find(self.node(i, j, n)) == uf.find(dummyNode):
board[i][j] = 'O'
else:
board[i][j] = 'X'
def node(self, i, j, n):
return i * n + j;
class UnionFind(object):
def __init__(self, n):
self.count = n
self.ids = [i for i in range(n)]
self.sz = [1 for i in range(n)]
def union(self, p, q):
i = self.find(p)
j = self.find(q)
if i == j:
return
elif self.sz[i] < self.sz[j]:
self.ids[i] = j
self.sz[j] += self.sz[i]
self.count -= 1
else:
self.ids[j] = i
self.sz[i] += self.sz[j]
self.count -= 1
def find(self, p):
while self.ids[p] != p:
self.ids[p] = self.ids[self.ids[p]]
p = self.ids[p]
return p
def count(self):
return self.count