Problem Link:
http://oj.leetcode.com/problems/surrounded-regions/
We can do follows in the 2D board.
Use BFS from all 'O' cells on the boundary and mark all connected 'O' cells
Scan the board and flip all unmarked 'O' to 'X'.
The following code is python code accepted by oj.leetcode.com.
class Solution:
# @param board, a 2D array
# Capture all regions by modifying the input board in-place.
# Do not return any value.
def solve(self, board):
"""
Let m and n be the number of rows and columns of board
BFS from 'O' nodes on the boundary
"""
# Special case 1: if m <= 2, then all cells are on the boundary
m = len(board)
if m <= 2:
return
# Special case 2: if n <= 2, then all cells are on the boundary
n = len(board[0])
if n <= 2:
return # Queue used for BFS
Q = [] # Find all 'O' cells in on the boundary
# check the first row and last row
for j in xrange(n):
if board[0][j] == 'O':
Q.append( (0,j) )
if board[m-1][j] == 'O':
Q.append( (m-1,j) )
# check the first column and last column
for i in xrange(1,m-1):
if board[i][0] == 'O':
Q.append( (i,0) )
if board[i][n-1] == 'O':
Q.append( (i,n-1) ) # Start BFS from the nodes in Q
# Each time set the node to "M",
# which means the node is not captured
while Q:
new_Q = []
for (i,j) in Q:
board[i][j] = 'M'
# Check left node
if i > 0 and board[i-1][j] == 'O':
new_Q.append( (i-1,j) )
# Check right node
if i < m-1 and board[i+1][j] == 'O':
new_Q.append( (i+1,j) )
# Check top node
if j > 0 and board[i][j-1] == 'O':
new_Q.append( (i, j-1) )
# Check bottom node
if j < n-1 and board[i][j+1] == 'O':
new_Q.append( (i, j+1) )
Q = new_Q # Scan the 2D board
# 1) set node of O to X
# 2) set node of OO to O
for i in xrange(m):
for j in xrange(n):
if board[i][j] == 'O':
board[i][j] = 'X'
if board[i][j] == 'M':
board[i][j] = 'O'