AcWing 173. 矩阵距离-python
原题链接
简单
作者:
小辉_9
,
2020-08-16 22:27:15
,
所有人可见
,
阅读 576
import collections
n, m = map(int, input().split())
g = []
for _ in range(n):
g.append(list(input()))
dist = [[-1] * (m) for _ in range(n)]
q = collections.deque()
for i in range(n):
for j in range(m):
if g[i][j] == "1":
q.append([i, j])
dist[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while q:
x, y = q.popleft()
for i in range(4):
newx = x + dx[i]
newy = y + dy[i]
if 0 <= newx < n and 0 <= newy < m and dist[newx][newy] == -1:
q.append([newx, newy])
dist[newx][newy] = dist[x][y] + 1
for i in range(len(dist)):
print(" ".join(map(str, dist[i])))