题目描述

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

$$\text{dist}(i,j,k,l) = |i-k| + |j-l|$$

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

$$B[i][j] = \min_{1 \le x \le N, 1 \le y \le M, A[x][y] = 1} \text{dist}(i,j,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

样例解释

输入矩阵 $A$：

0 0 0 1
0 0 1 1
0 1 1 0

值为 1 的位置有：(1,4), (2,3), (2,4), (3,2), (3,3)

对于每个位置 $(i,j)$，计算它到最近的值为 1 的位置的曼哈顿距离。

例如：

• (1,1) 到最近的 1 是 (1,4)，距离 |1-1| + |1-4| = 3
• (3,4) 到最近的 1 是 (2,4)，距离 |3-2| + |4-4| = 1
• (3,1) 到最近的 1 是 (3,2)，距离 1

输出矩阵 $B$ 如上。

数据范围

• $1 \le N, M \le 1000$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB