Just traverse the matrix one by one with using recursive method. Union-Find helps it to record connected component. Then, rule out those components touching the boundaries and flip `O`

to `X`

.

```
class UnionFind():
def __init__(self, m, n):
self.dad = [i for i in xrange(0, m*n)]
self.rank = [0 for i in xrange(0, m*n)]
self.m = m
self.n = n
def find(self, x):
dad = self.dad
if dad[x] != x:
dad[x] = self.find(dad[x])
return dad[x]
def union(self, xy):
dad = self.dad
rank = self.rank
x, y = map(self.find, xy)
if x == y:
return False
if rank[x] > rank[y]:
dad[y] = x
else:
dad[x] = y
if rank[x] == rank[y]:
rank[y] += 1
return True
class Solution:
def solve(self, board):
if len(board) == 0:
return board
regions = set([])
n, m = len(board), len(board[0])
uf = UnionFind(len(board[0]), len(board))
directions = {"d": (1, 0), "r": (0, 1)}
for i in xrange(0, len(board)):
for j in xrange(0, len(board[0])):
if board[i][j] == 'X':
continue
for d in ["d", "r"]:
di, dj = directions[d]
newi, newj = i + di, j + dj
if newi >= 0 and newi < len(board) and newj >= 0 and newj < len(board[0]):
if board[newi][newj] == "O":
uf.union((newi*m + newj, i*m + j))
for i in xrange(0, len(board)):
for j in [0, len(board[0]) - 1]:
if board[i][j] == "O":
regions.add(uf.find(i*m + j))
for j in xrange(0, len(board[0])):
for i in [0, len(board) - 1]:
if board[i][j] == "O":
regions.add(uf.find(i*m + j))
for i in xrange(0, len(board)):
for j in xrange(0, len(board[0])):
if board[i][j] == "O" and uf.find(i*m + j) not in regions:
board[i][j] = "X"
```