# AC Python 140 ms solution, BFS starting from boundary 'O'

• ``````displacements = [[1, 0], [-1, 1], [-1, -1], [1, -1]]
# (i,j) -> (i+1,j) -> (i,j+1) -> (i-1,j) -> (i,j-1)

def bfs(self, board, i, j, m, n):
# O: White, X:Black, G:Gray
dq = collections.deque([[i, j]])
board[i][j] = 'G'
while dq:
i, j = dq.popleft()
for di, dj in Solution.displacements:
i += di
j += dj
if 0 <= i < m and 0 <= j < n and board[i][j] == 'O':
dq.append([i, j])
board[i][j] = 'G'

def solve(self, board):
if len(board) < 3 or len(board[0]) < 3:
return
m, n = len(board), len(board[0])
for i in xrange(m):
for j in 0, n - 1:
if board[i][j] == 'O':
self.bfs(board, i, j, m, n)

for i in 0, m - 1:
for j in xrange(1, n - 1):
if board[i][j] == 'O':
self.bfs(board, i, j, m, n)

for row in board:
for j in xrange(n):
if row[j] != 'X':
row[j] = 'X' if row[j] == 'O' else 'O'

# 58 / 58 test cases passed.
# Status: Accepted
# Runtime: 140 ms
# 94.63%
``````

The idea is to color all non surrounded region and then flip those uncolored ones. Any non surrounded region must connect to a 'O' at the boundary. Therefore we can perform BFS from boundary 'O's. This way we minimized our search task.

• Here I have a problem, why do you keep incrementing i and j in each direction?
My understanding is that you should do something like

``````for di, dj in Solution.displacements:
tmpi = i + di
tmpj = j + dj
``````

to avoid i, and j being in the wrong direction

``````for di, dj in Solution.displacements:
i += di
j += dj
``````

• If i did wrong i won't get AC right?

I know it is a bit of confusing here. Thanks for asking.

I did use a trick, note that I didn't use `directions` which should be:

``````directions = [[1, 0], [-1,0], [0,1],[0,-1]]
``````

``````displacements = [[1, 0], [-1, 1], [-1, -1], [1, -1]]