# It's like a story

• Those area connecting to the borders should not be modified. To do this:

1. protect the border connecting area (BFS starting from the four border lines)
2. kill those unprotected 'O's
3. bring back the protected area
``````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

dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
def mark(i, j, chr):
queue = [(i, j)]
while queue:
top = queue.pop()
i, j = top[0], top[1]
if not ( 0 <= i < len(board) and 0 <= j < len(board[0]) ) or board[i][j] != 'O':
continue
board[i][j] = chr
for l in xrange(len(dir)):
queue.append( (i + dir[l][0], j + dir[l][1]) )

#protect left, right vertical borders
for i in xrange(len(board)):
if board[i][0] == 'O':
mark(i, 0, '1')
if board[i][len(board[0]) - 1] == 'O':
mark(i, len(board[0]) - 1, '1')

#protect top, bottom horizontal borders
for i in xrange(len(board[0])):
if board[0][i] == 'O':
mark(0, i, '1')
if board[len(board) - 1][i] == 'O':
mark(len(board) - 1, i, '1')

#kill un-protected nodes
for i in xrange(len(board)):
for j in xrange(len(board[0])):
if board[i][j] == 'O':
board[i][j] = 'X'
#bring back the protected nodes
for i in xrange(len(board)):
for j in xrange(len(board[0])):
if board[i][j] == '1':
board[i][j] = 'O'
``````

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