给定一个二维的矩阵，包含 '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'
