原题
给一个二维的矩阵，包含 'X' 和 'O', 找到所有被 'X' 围绕的区域，并用 '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
X O X X
解题思路
- 通过分析可知，就是要将所有以O组成、但没有连通到网格边缘的区域变为X。
- 所以可以沿着四个边找O，找到每一个O就把相连的都变成Y，因为 他们都是要保留的，最后遍历二维数组，遇到O变成X，遇到Y变回O
- 具体方法可以采用BFS, DFS, Union Find，但是DFS大数据会爆栈，DFS最快
完整代码
import Queue
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
def fill(x, y):
if x < 0 or x > height-1 or y < 0 or y > width-1 or board[x][y] != "O":
return
MyQueue.put((x, y))
board[x][y] = "D"
def bfs(x, y):
if board[x][y] == "O":
fill(x, y)
while not MyQueue.empty():
current = MyQueue.get()
i, j = current[0], current[1]
fill(i+1, j)
fill(i-1, j)
fill(i, j+1)
fill(i, j-1)
if len(board) == 0:
return
height, width, MyQueue = len(board), len(board[0]), Queue.Queue()
for i in range(width):
bfs(0, i)
bfs(height - 1, i)
for j in range(1, height - 1):
bfs(j, 0)
bfs(j, width - 1)
for i in range(height):
for j in range(width):
if board[i][j] == "D":
board[i][j] = "O"
elif board[i][j] == "O":
board[i][j] = "X"
