解题思路

1. 题目要求每个格子到最近字符 $0$ 的最短步数，移动方式是上下左右四联通，因此这是网格图上的最短路问题。
2. 如果对每个格子单独 BFS，会变成 $O((nm)^2)$，在 $n,m \le 10^3$ 时无法通过。
3. 可以把所有字符 $0$ 的格子同时加入队列，距离设为 $0$，然后做一次多源 BFS。BFS 按距离从小到大扩展，所以每个字符 $1$ 第一次被访问到时，得到的就是它到最近字符 $0$ 的距离。
4. 用 dist[i][j] = -1 表示还没有计算过距离。每次从队头取出一个格子，尝试扩展四个相邻格子，若相邻格子尚未访问，就令它的距离等于当前距离加 $1$ 并入队。

复杂度分析

题目内容

给定一张由 $n$ 行、$m$ 列组成的地图。用字符 $'0'$ 表示天才同学的别墅位置，用字符 $'1'$ 表示其他位置。对于地图上的每一个位置，定义其到最近别墅的距离为：从该位置出发，每次可以向上、下、左、右四个方向走一步（只能走到相邻的位置），到达任意一个 $'0'$ 所需要的最少步数。若该位置本身就是 $'0'$，则距离为 $0$。

输入描述

在一行上输入两个整数 $n, m\ (1 \le n, m \le 10^3)$，表示地图的行数与列数。

此后 $n$ 行，每行输入一个长度为 $m$ 的字符串 $s_i$，仅由字符 $'0'$ 和 $'1'$ 组成。保证至少存在一个位置为 $'0'$。

输出描述

输出 $n$ 行。第 $i$ 行输出 $m$ 个整数，分别表示第 $i$ 行每个位置到最近 $'0'$ 的最短步数。相邻整数之间使用一个空格分隔。

样例1

输入

3 4
0111
0011
1111

输出

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