有一个由数字 0、1 组成的方阵中,存在一任意形状的封闭区域,封闭区域由数字1 包围构成,每个节点只能走上下左右 4 个方向。现要求把封闭区域内的所有空间都填写成2 .例如: 6×6 的方阵:
时间: 2023-05-03 13:02:13 浏览: 116
题目描述:有一个由数字 0、1 组成的数组成的方阵,在一个任意意形状的封闭区域,封闭区域由数字1 包围,封闭区域由数字1 包围的区域由数字1 包围,每个节 点只能走上下左右 4 个方向。现要求把封闭区域内的所有空间都填写为数字 2,例如:6×6 的方阵:
考虑使用深度优先搜索实现,从外围开始寻找,找到 1 就将其置为2,然后继续遍历其上下左右四个方向,直到遇到边界或 1 为止。
实现代码如下:
```python
def dfs(matrix, row, col):
# 判断点是否已经越界或者已经是封闭区间(被遍历过了)
if row < 0 or row >= len(matrix) or col < 0 or col >= len(matrix[0]) or matrix[row][col] != 1:
return
else:
# 将点标记为封闭区间
matrix[row][col] = 2
# 分别遍历四个方向
dfs(matrix, row - 1, col)
dfs(matrix, row + 1, col)
dfs(matrix, row, col - 1)
dfs(matrix, row, col + 1)
def fill_matrix(matrix):
# 遍历第一行和最后一行
for i in range(len(matrix[0])):
dfs(matrix, 0, i)
dfs(matrix, len(matrix) - 1, i)
# 遍历第一列和最后一列
for i in range(len(matrix)):
dfs(matrix, i, 0)
dfs(matrix, i, len(matrix[0]) - 1)
# 填充空间
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 1:
matrix[i][j] = 2
```
例如:
```python
matrix = [
[1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 1],
[1, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1]]
fill_matrix(matrix)
for row in matrix:
print(row)
```
输出:
```python
[1, 0, 0, 0, 0, 1]
[1, 2, 1, 1, 0, 1]
[1, 2, 1, 1, 0, 1]
[1, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 1]
```