请给出python代码: 存在一个m*n的二维数组,其成员取值范围为0或1。其中值为1的成员具备扩散性, 每经过1S,将上下左右值为0的成员同化为1。 二维数组的成员初始值都为0,将第[i,j]和[k,l]两个位置上元素修改成1后,求矩阵的所有元素变为1需要多长时间。 输入描述: 前两个数是矩阵m*n,中间两个数是第一个点的坐标,最后两个数是第二个点的坐标 其中这两个点初始为1,其他点初始为0 输出描述: 输出矩阵的所有元素变为1所需要秒数。
时间: 2023-11-27 16:51:53 浏览: 86
华为OD机试矩阵扩散问题,
5星 · 资源好评率100%
以下是实现该功能的Python代码:
```
import queue
def bfs(grid, q):
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while not q.empty():
r, c, t = q.get()
for d in directions:
nr, nc = r + d[0], c + d[1]
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 0:
grid[nr][nc] = 1
q.put((nr, nc, t + 1))
m, n, x1, y1, x2, y2 = map(int, input().split())
grid = [[0] * n for _ in range(m)]
grid[x1-1][y1-1] = 1
grid[x2-1][y2-1] = 1
q = queue.Queue()
q.put((x1-1, y1-1, 0))
q.put((x2-1, y2-1, 0))
bfs(grid, q)
max_t = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
return -1
max_t = max(max_t, grid[i][j])
print(max_t)
```
该代码使用了宽度优先搜索(BFS)算法,实现了对二维数组的遍历并标记已经被扩散的元素。时间复杂度为O(mn)。
阅读全文