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