# Is there any better solution?

• 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``````

• I use BFS In Java, 560 ms.

``````public class Solution {
public static void solve(char[][] board) {
if (board == null || board.length == 0)
return;
int m = board.length;
int n = board[0].length;
boolean visited[][] = new boolean[m][n];
int dir[][] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {

//bfs
if (board[i][j] == 'O' && !visited[i][j]) {
boolean surounned = true;
List<Integer> visitedPoints = new ArrayList<Integer>();
visited[i][j] = true;
while (queue.size() > 0) {
int point = queue.poll();
int x = point/n;
int y = point%n;
for (int k = 0; k < 4; k++) {
int nextx = x + dir[k][0];
int nexty = y + dir[k][1];
if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
if (board[nextx][nexty] == 'O' && !visited[nextx][nexty])
visited[nextx][nexty] = true;
} else {
surounned = false;
}
}
}

if (surounned) {
for (int p : visitedPoints)
board[p / n][p % n] = 'X';
}
}
}
}
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.