130. Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

解题要点：

首先把边界的‘O'以及与其相邻的’O'全变为不有效字符（在此我用‘#’），来处理不被包围的’O'。然后把其他‘O'全部转换为’X'（被包围的‘O'），最后把‘#’改回‘O'。

class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        if board == None or len(board) == 0:
            return
        n = len(board)
        m = len(board[0])
        def search(board, i, j):
            queue = [(i, j)]
            while queue:
                r, c = queue.pop(0)
                if r - 1 >= 0 and board[r-1][c] == 'O':
                    board[r-1][c] = '#'
                    queue.append((r-1,c))
                if r + 1 < n and board[r+1][c] == 'O':
                    board[r+1][c] = '#'
                    queue.append((r+1,c))
                if c - 1 >= 0 and board[r][c-1] == 'O':
                    board[r][c-1] = '#'
                    queue.append((r,c-1))
                if c + 1 < m and board[r][c+1] == 'O':
                    board[r][c+1] = '#'
                    queue.append((r,c+1))
        for i in range(n):
            for j in range(m):
                if i == 0 and board[i][j] == 'O':
                    board[i][j] = '#'
                    search(board, i, j)
                if i == n-1 and board[i][j] == 'O':
                    board[i][j] = '#'
                    search(board, i, j)
                if i > 0 and i < n-1 and j == 0 and board[i][j] == 'O':
                    board[i][j] = '#'
                    search(board, i, j)
                if i > 0 and i < n-1 and j == m-1 and board[i][j] == 'O':
                    board[i][j] = '#'
                    search(board, i, j)
        for i in range(n):
            for j in range(m):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
        for i in range(n):
            for j in range(m):
                if board[i][j] == '#':
                    board[i][j] = 'O'