给定一个二维的矩阵，包含 '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
1、题目分析
题目的要求比较简单了，就是如果X把O都围起来，那么就把围起来的O都变成X。如果没有被围，那么原定的O不会变。从题目的角度来分析，我们其实需要从最外面的四条边来出发，如果四条边都是X，没O那就说明这个四条边围的O都需要变成X来处理，如果右O的话，作为一个突破口，不断的去观察，然后标记与O相邻的O。知道没有与O相邻的O出现，标记就完成了。然后对给定的二维矩阵重新左更改，对于标记的都变成O，没有标记的都变成X。
2、解题分析
- 对给定数组进行判断，行列都是小于等于2直接结束，因为不可能把O围住
- 对于一个二维矩阵最外面的那一圈进行判断，如果是'O'那就添加到队列最中，并做标记
- 接下来就是BFS的模板，每个位置移动的方向就是左中上下
- 对新位置进行判断，是不是在矩阵中
- 对新位置进行判断，是不是‘O’
- 如果上述两个条件同时满足，那就标记’O‘，且把'O'添加到对立中去
- 重复上述操作，直至为队列为空
- 修该数组中的’O‘
- 如果数组中该位置被标记过，就是’O‘
- 如果数组中该位置未被标记，就是'X'
3、代码
class Solution:def solve(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""queue = collections.deque()m = len(board)if m<=2:return n = len(board[0])if n<=2:return#对数组进行标记，且把‘O’的位置添加到队列中for i in range(m):if board[i][0]=='O':board[i][0]='.'queue.append((i,0))if board[i][n-1]=='O':board[i][n-1]='.'queue.append((i,n-1))for i in range(n):if board[0][i]=='O':board[0][i]='.'queue.append((0,i))if board[m-1][i]=='O':board[m-1][i]='.'queue.append((m-1,i))#BFS模板while queue:x,y = queue.popleft()zuobiao = [(1,0),(0,1),(-1,0),(0,-1)]for xd,yd in zuobiao:X,Y = x+xd,y+ydif 0<=X<m and 0<=Y<n and board[X][Y]=='O':board[X][Y]='.'queue.append((X,Y))print(board)#通过标记修改数组for i in range(m):for j in range(n):if board[i][j]=='O':board[i][j]='X'if board[i][j]=='.':board[i][j]='O'
总结：典型的迷宫，岛屿问题，这种问题都是需要使用BFS模板。