13 - Hard - 被围绕的区域

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X
解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

方法一，从四周的点开始遍历，如果为O再把该点上下左右的点加入遍历队列

Phase 1: "Save" every O-region touching the border, changing its cells to 'S'.
Phase 2: Change every 'S' on the board to 'O' and everything else to 'X'.

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 any(board): 
            return
        m, n = len(board), len(board[0])
        save = [ij for k in range(max(m, n)) for ij in ((0, k), (m-1, k), (k, 0), (k, n-1))]
        while save:
            i, j = save.pop()
            if 0 <= i < m and 0 <= j < n and board[i][j] == 'O':
                board[i][j] = 'S'
                save += (i, j-1), (i, j+1), (i-1, j), (i+1, j)

        board[:] = [['XO'[c == 'S'] for c in row] for row in board]

更详细的BFS

class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """

        def BFS(matrix, index_i, index_j):
            stack = [[index_i, index_j]]
            steps = [[-1, 0], [1, 0], [0, -1], [0, 1]]

            while stack:
                tmp_point = stack.pop()
                matrix[tmp_point[0]][tmp_point[1]] = '-1'
                for step in steps:
                    right_i = tmp_point[0] + step[0]
                    right_j = tmp_point[1] + step[1]
                    if right_i >= 0 and right_i < len(matrix) and right_j >= 0 and right_j < len(matrix[0]) \
                            and matrix[right_i][right_j] == 'O':
                        stack.append([right_i, right_j])

            return matrix

        if board != []:
            for i in range(0, len(board)):
                if board[i][0] == 'O':
                    board = BFS(board, i, 0)
                if board[i][len(board[0]) - 1] == 'O':
                    board = BFS(board, i, len(board[0]) - 1)

            for j in range(0, len(board[0])):
                if board[0][j] == 'O':
                    board = BFS(board, 0, j)
                if board[len(board) - 1][j] == 'O':
                    board = BFS(board, len(board) - 1, j)

            for i in range(0, len(board)):
                for j in range(0, len(board[0])):
                    if board[i][j] == 'O':
                        board[i][j] = 'X'
                    if board[i][j] == '-1':
                        board[i][j] = 'O'