This my solution about the problem and I do it in-place. I use DFS to travel the graph. I change the content to contain the parent infomation. I cost about 556 ms. Is there any better solution?

```
class Solution:
def print_maxtrix(self, board):
x_length = len(board)
y_length = len(board[0])
x = 0
while x < x_length:
y = 0
s = ''
while y < y_length:
s += board[x][y] + ' '
y += 1
print s
x += 1
def do_paint(self, board, x, y, curr_x, curr_y):
while not(curr_x == x and curr_y == y):
if (curr_x > 0) and (board[curr_x-1][curr_y] == 'O'):
board[curr_x-1][curr_y] = 'C'
curr_x -= 1
continue
if (curr_x < len(board) - 1) and (board[curr_x + 1][curr_y] == 'O'):
board[curr_x+1][curr_y] = 'A'
curr_x += 1
continue
if (curr_y > 0) and (board[curr_x][curr_y-1] == 'O'):
board[curr_x][curr_y-1] = 'D'
curr_y -= 1
continue
if (curr_y < len(board[0]) - 1) and (board[curr_x][curr_y + 1] == 'O'):
board[curr_x][curr_y+1] = 'B'
curr_y += 1
continue
if board[curr_x][curr_y] == 'A':
curr_x -= 1
elif board[curr_x][curr_y] == 'B':
curr_y -= 1
elif board[curr_x][curr_y] == 'C':
curr_x += 1
elif board[curr_x][curr_y] == 'D':
curr_y += 1
def paint_graph(self, board, x, y):
board[x][y] = 'E'
if (x > 0) and (board[x-1][y] == 'O'):
board[x-1][y] = 'C'
self.do_paint(board, x, y, x-1, y)
if (x < len(board) -1) and (board[x+1][y] == 'O'):
board[x+1][y] = 'A'
self.do_paint(board, x, y, x+1, y)
if (y > 0) and (board[x][y-1] == 'O'):
board[x][y-1] = 'D'
self.do_paint(board, x, y, x, y-1)
if (y < len(board[0]) - 1) and (board[x][y+1] == 'O'):
board[x][y+1] = 'B'
self.do_paint(board, x, y, x, y+1)
# @param board, a 2D array
# Capture all regions by modifying the input board in-place.
# Do not return any value.
def solve(self, board):
x_length = len(board)
if x_length == 0: return
y_length = len(board[0])
if y_length == 0: return
# travel the outside cycle
# top line
curr = 0
while curr < y_length:
if board[0][curr] == 'O':
self.paint_graph(board, 0, curr)
curr += 1
# right line
curr = 0
while curr < x_length:
if board[curr][y_length-1] == 'O':
self.paint_graph(board, curr, y_length-1)
curr += 1
#bottom line
curr = y_length - 1
while curr >= 0:
if board[x_length-1][curr] == 'O':
self.paint_graph(board, x_length-1, curr)
curr -= 1
# left line
curr = x_length - 1
while curr >= 0:
if board[curr][0] == 'O':
self.paint_graph(board, curr, 0)
curr -= 1
#print 'after paint'
#self.print_maxtrix(board)
# change the graph
x = 0
while x < x_length:
y = 0
while y < y_length:
if board[x][y] == 'O':
board[x][y] = 'X'
elif board[x][y] != 'X':
board[x][y] = 'O'
y += 1
x += 1
```