题目描述

给定一个$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]) $$

输入格式

第一行两个整数 $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

数据范围

$1≤N,M≤1000$

来源

• BZOJ2252
• 算法竞赛进阶指南