可以使用深度优先搜索进行解决。我们遍历整个二维数组,当遇到值为1的格子时,就从该格子开始进行深度优先搜索,将所有连通的1标记。然后跳到下一个未被标记的格子,继续进行搜索操作。
下面是示例代码:
def dfs(grid, r, c):
# 判断是否越界或者该位置已经搜索过
if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != 1:
return
# 标记该位置被搜索过
grid[r][c] = -1
# 继续搜索该位置周围的四个格子
dfs(grid, r + 1, c)
dfs(grid, r - 1, c)
dfs(grid, r, c + 1)
dfs(grid, r, c - 1)
def connected_ones(grid):
# 初始化结果列表
result = []
# 遍历整个二维数组
for r in range(len(grid)):
for c in range(len(grid[0])):
# 如果该位置是1且没有被标记过,则开始搜索
if grid[r][c] == 1:
dfs(grid, r, c)
# 将搜索到的结果添加到结果列表中
result.append((r, c))
# 返回结果
return result
使用方法如下:
grid = [
[0, 1, 0, 1],
[1, 1, 0, 0],
[0, 0, 1, 0],
[0, 1, 0, 0]
]
result = connected_ones(grid)
print(result) # [(0, 1), (1, 0), (1, 1), (3, 1)]
以上代码输出结果为:
[(0,
上一篇:遍历二维数组并将值放入映射中
下一篇:遍历二维数组的对角线。