题目内容

在一个由 $n$ 行 $m$ 列构成的矩形区域中，每个格子可能是庇护所或空地。我们用字符 0 表示庇护所，字符 1 表示空地。对于区域里的每一个格子，定义其到最近庇护所的距离为：从该格子出发，每次可以向上、下、左、右走一格，到达任意一个 0 所需的最少步数。若格子本身就是 0，则距离为 $0$。

行数 $n$ 与列数 $m$ 满足 $1 \le n, m \le 10^3$。输入的字符串仅包含字符 0 和 1，且保证至少存在一个 0。

输入描述

第一行包含两个整数 $n$ 和 $m$，表示区域的行数与列数。 接下来的 $n$ 行，每行一个长度为 $m$ 的字符串，仅由字符 0 和 1 组成。

输出描述

输出共 $n$ 行。第 $i$ 行输出 $m$ 个整数，分别表示第 $i$ 行每个格子到最近庇护所的最少步数，相邻整数之间用一个空格分隔。

样例1

输入

3 3
011
111
111

输出

0 1 2
1 2 3
2 3 4

说明

区域中只有一个庇护所，位于左上角 (1,1)（字符 0），其余格子均为空地（字符 1）。

最近距离：

• 庇护所自身距离为 $0$。
• 第一行剩下格子依次距离为 $1$、$2$。
• 第二行距离为 $1$、$2$、$3$。
• 第三行距离为 $2$、$3$、$4$。

可以看出，距离从左上角逐步向外递增。

样例2

输入

2 2
00
00

输出

0 0
0 0

说明

所有格子都是庇护所（字符 0）。每个格子本身就是庇护所，因此到最近庇护所的距离均为 $0$。这是最平凡的边界情况。

样例3

输入

1 5
01010

输出

0 1 0 1 0

说明

在一行中，庇护所位于第 1、3、5 个位置（字符 0），它们之间交替出现空地（字符 1）。

每个庇护所自身距离为 $0$，相邻的空地由于紧挨庇护所，距离为 $1$。因此输出从左到右依次为 $0, 1, 0, 1, 0$。

样例4

输入

3 4
0101
1010
0101

输出

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

说明

区域中有多个庇护所交错分布，形成棋盘状。

• 第一行：位置 (1,1) 和 (1,3) 是庇护所，距离 $0$；位置 (1,2) 与 (1,4) 紧邻庇护所，距离 $1$。
• 第二行：全为空地，但上下左右均有相邻庇护所，因此所有格子的最近距离均为 $1$。
• 第三行：与第一行对称，输出 $0, 1, 0, 1$。

这种布局展示了在密集庇护所情况下，距离被很好地限制在较小值。