Python实战操作：解题之被围绕的区域
题目
给定一个二维的矩阵，包含 ‘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’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
解题思路
思路：DFS、BFS
首先先看题目，给定的二维矩阵中，包含 ‘X’ 和 ‘O’（ 字母 O）。再看解释部分，任何边界上的 ‘O’ 不会被填充为 ‘X’，那么现在也就是说，其实有三个部分：
- 可形成包围的 ‘X’；
- 被 ‘X’ 包围的 ‘O’；
- 未被 ‘X’ 包围的 ‘O’。
现在题目的要求是将被包围的 ‘O’，转变为 ‘X’。前面也说了，未被包围的 ‘O’，是处于边界上的，同时侧面说明与边界 ‘O’ 相连的 ‘O’ 又不会被 ‘X’ 填充。
那么我们可以根据这个性质，我们考虑从边界开始扩散，先去标记不能被填充的 ‘O’，也就是与边界 ‘O’ 相连的部分，那么剩下的 ‘O’ 则会被包围转变为 ‘X’。具体的做法如下：
- 以边界的 ‘O’ 为起点，标记与之相连或者间接相连的字母 ‘O’；
- 当标记完上面部分的 ‘O’，此时开始遍历矩阵，去判断每个字母（注意：标记的为不会被替换的部分）：如果该字母是被标记的部分，那么将其重新转换为 ‘O’；如果该字母是未被标记的部门，那么将其转换为 ‘X’。
注意：题目要求的是原地修改，那么我们标记的时候，将与边界 ‘O’ 相连的部分（包括边界 ‘O’），标记为 ‘M’。
我们现在使用深度优先搜索（DFS）和广度优先搜索（BFS）的方法来解决这个问题。具体的代码如下。
代码实现
#深度优先搜索（DFS）
class Solution:
def solve(self, board: List[List[str]]) -> None:
""
"
Do not return anything, modify board in-place instead.
"
""
if not board or
len(board)==
0:
return
def dfs(board, i, j):
# 不处于矩阵内，或者如果已经标记的话，直接跳过
if not (
0<=i<m) or not (
0<=j<n) or board[i][j] !=
'O':
return
# 当确认为未标记的，并与边界
'O' 直接间接相连的
'O' 时，标记为
'M'
board[i][j] =
'M'
# 向四个方位扩散
# 上下左右
dfs(board, i
-1, j)
dfs(board, i+
1, j)
dfs(board, i, j
-1)
dfs(board, i, j+
1)
m =
len(board)
n =
len(board[
0])
# 从边界的
'O' 开始搜索
for i in
range(m):
for j in
range(n):
# 先确认 i，j 是否处于边界
is_frontier = (i ==
0 or j ==
0 or i == m
-1 or j == n
-1)
if is_frontier and board[i][j] ==
'O':
dfs(board, i, j)
# 遍历二维数组，将被标记为
'M' 的重新转换为
'O'，未标记的，则转换为
'X'
for i in
range(m):
for j in
range(n):
if board[i][j] ==
'O':
board[i][j] =
'X'
if board[i][j] ==
'M':
board[i][j] =
'O'
# 广度优先搜索（BFS）
class Solution:
def solve(self, board: List[List[str]]) -> None:
""
"
Do not return anything, modify board in-place instead.
"
""
if not board or
len(board) ==
0:
return
m =
len(board)
n =
len(board[
0])
from collections
import deque
queue = deque()
# bfs 不同于 dfs 顺着满足条件的方向继续搜索
# bfs 满足条件的都要入队列
# 先将边界的
'O' 入队
for i in
range(m):
# 这里是二维矩阵的最左列与最右列
if board[i][
0] ==
'O':
queue.
append((i,
0))
if board[i][n
-1] ==
'O':
queue.
append((i, n
-1))
for j in
range(n):
# 这里是二维矩阵的第一行和最后一行
if board[
0][j] ==
'O':
queue.
append((
0, j))
if board[m
-1][j] ==
'O':
queue.
append((m
-1, j))
# 现在开始出队，目前里面的都是边界的
'O'
# 出队的同时，进行标记，同时查找与边界
'O' 相连的部分入队
while queue:
x, y = queue.popleft()
board[x][y] =
'M'
# 查找相连部分
for nx, ny in [(x
-1, y), (x+
1, y), (x, y
-1), (x, y+
1)]:
if
0 <= nx < m and
0 <= ny < n and board[nx][ny] ==
'O':
queue.
append((nx, ny))
# 同样的，标记完后，遍历整个二维矩阵，进行转换
for i in
range(m):
for j in
range(n):
if board[i][j] ==
'O':
board[i][j] =
'X'
if board[i][j] ==
'M':
board[i][j] =
'O'
结果大家可以自己动手实现一下哦！
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/69923331/viewspace-2711544/ ，如需转载，请注明出处，否则将追究法律责任。
