130. 被围绕的区域
Tags: DFS, BFS
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
注意：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
转换思路，寻找被包围的'O'是相对困难的，由于题目提示了边界上的'O'和与边界上的'O'相连的'O'不会被填充，因此接下来的任务就是寻找边界上的'O'和与边界上的'O'相连的'O'，并把这些'O'替换为其它符号，如'#'。然后遍历整个矩阵，将剩余的'O'替换为'X'，将'#'替换为'O'。
- 递归版DFS
class Solution:
def solve(self, board: List[List[str]]) -> None:
if len(board) == 0:
return
# 递归dfs
for i in range(len(board)):
if board[i][0] == 'O':
self.dfs(board, i, 0)
if board[i][len(board[0])-1] == 'O':
self.dfs(board, i, len(board[0]) - 1)
for j in range(len(board[0])):
if board[0][j] == 'O':
self.dfs(board, 0, j)
if board[len(board)-1][j] == 'O':
self.dfs(board, len(board)-1, j)
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '#':
board[i][j] = 'O'
def dfs(self, board, i, j):
if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or board[i][j] == 'X' or board[i][j] == '#':
return
board[i][j] = '#'
self.dfs(board, i-1, j)
self.dfs(board, i, j-1)
self.dfs(board, i+1, j)
self.dfs(board, i, j+1)
- 非递归版DFS（使用栈）
class Solution:
def solve(self, board: List[List[str]]) -> None:
if len(board) == 0:
return
stack = []
for i in range(len(board)):
if board[i][0] == 'O':
stack.append((i, 0))
if board[i][len(board[0])-1] == 'O':
stack.append((i, len(board[0]) - 1))
for j in range(len(board[0])):
if board[0][j] == 'O':
stack.append((0, j))
if board[len(board)-1][j] == 'O':
stack.append((len(board)-1, j))
while stack:
i, j = stack.pop(-1)
board[i][j] = '#'
for d_i, d_j in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
if i + d_i < 0 or j + d_j < 0 or i + d_i >= len(board) or j + d_j >= len(board[0]) or board[i+d_i][j+d_j] == 'X' or board[i+d_i][j+d_j] == '#':
continue
stack.append((i+d_i, j+d_j))
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '#':
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 len(board) == 0:
return
queue = []
for i in range(len(board)):
if board[i][0] == 'O':
queue.append((i, 0))
if board[i][len(board[0])-1] == 'O':
queue.append((i, len(board[0]) - 1))
for j in range(len(board[0])):
if board[0][j] == 'O':
queue.append((0, j))
if board[len(board)-1][j] == 'O':
queue.append((len(board)-1, j))
while queue:
i, j = queue.pop(0)
board[i][j] = '#'
for d_i, d_j in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
if i + d_i < 0 or j + d_j < 0 or i + d_i >= len(board) or j + d_j >= len(board[0]) or board[i+d_i][j+d_j] == 'X' or board[i+d_i][j+d_j] == '#':
continue
queue.append((i+d_i, j+d_j))
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '#':
board[i][j] = 'O'
