3486. [BZOJ 2250]矩阵距离

【题目描述】

给定一个 $N$ 行 $M$ 列的 $01$ 矩阵 $A$，$A[i][j]$ 与 $A[k][l]$ 之间的曼哈顿距离定义为：

$dist(A[i][j],A[k][l]) = |i-k|+|j-l|$

输出一个N行M列的整数矩阵 $B$，其中：

$B[i][j]=min(1≤x≤N,1≤y≤M,A[x][y]=1)⁡{dist(A[i][j],A[x][y])}$

即求与每个位置曼哈顿距离最近的 $1$，$N,M≤1000$。

【输入格式】

第一行两个整数 $n,m$。

接下来一个 $N$ 行 $M$ 列的 $01$ 矩阵，数字之间没有空格。

【输出格式】

一个 $N$ 行 $M$ 列的矩阵 $B$，相邻两个整数之间用一个空格隔开。

【样例输入】

3 4
0001
0011
0110

【样例输出】

3 2 1 0
2 1 0 0
1 0 0 1

【来源】

《算法竞赛进阶指南》
BZOJ2250