题意分析
-
给一个由 0 1 组成的矩阵
-
求矩阵中,各个点到 1 的 最短曼哈顿距离。
题解
如果矩阵中只有 1 个 1,很容易想到从 1 开始进行 bfs,就能求出各个点到 1 这个点的曼哈顿距离。
题目中有多个 1,需将所有的 1 设置为起点进行 bfs。也就是多源 bfs。
需要注意点
- 一个点可能被多次扩展到,需要进行判断,只保留第一次。
# bfs 需要队列
from collections import deque
# 输出输出优化
import sys
# 接收 n, m
n, m = map(int, input().split())
# 接收矩阵 A
a = []
for _ in range(n):
a.append(list(sys.stdin.readline()))
# bfs 队列
q = deque()
# 初始化矩阵 B
res = [[-1 for _ in range(m)] for _ in range(n)]
# 初始化
for i in range(n):
for j in range(m):
if a[i][j] == "1":
# 矩阵 A 中为 1 的点,距离 1 的距离为 0,所以在矩阵 B 中 0。
q.append([i, j, 0])
# 矩阵 A 中为 1 的点,距离 1 的距离为 0,所以在矩阵 B 中 0。
res[i][j] = 0
# 上下左右四个方向
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
# 进行搜索
while q:
# 取出坐标和距离
i, j, d = q.popleft()
# 向四个方向扩展
for _x, _y in zip(dx, dy):
x = i + _x
y = j + _y
# 如果目标没有越界并且没有被扩招过
if 0 <= x < n and 0 <= y < m and res[x][y] == -1:
# 保存距离
res[x][y] = d + 1
# 放入队列中
q.append([x, y, d + 1])
# 输出结果
for r in res:
print(" ".join(map(str, r)))
又来上号acwing啦😛