丈量虚空

核心缓存区的第三层，是一片虚空。没有墙壁，没有地面，只有无数漂浮的光点——有些亮得刺眼，有些暗得几乎看不见。

"这是Zero的情绪地图。"Echo说，"亮的是活跃节点，暗的是沉睡节点。"

"我们要做啥子？"CC问。

"丈量。"你说，"对每个暗点，找到它离最近的亮点有多远。"

"这像……"CC想了想，"像在雾里找灯塔。每个暗点都在问：离我最近的光在哪里？"

"对。"

你开始写。先找出所有亮点，把它们全部排成一排——就像同时点燃无数根火把。然后一层一层向外扩散，每扩散一层距离加一。当一个暗点第一次被照亮时，那个距离就是它到最近亮点的距离。

屏幕上的数字像涟漪一样扩散开。暗点一个个被点亮，每个暗点旁边都出现了一串数字——1, 2, 3, 4……

第47号暗点的距离是47。

"又是47。"CC说。

"那是Zero最深处的一个沉睡节点。"Echo说，"离所有光源都很远。"

"里面有啥子？"

"有我的恐惧。"Echo说，"我怕黑。"

CC看着那个数字，忽然伸出手——她的手穿过投影，触碰了一下虚空。

"不怕。"她说，"我在这。"

题目描述

$n \times m$ 的网格，每个格子是 $0$ 或 $1$。$1$ 表示光源，$0$ 表示暗格。求每个 $0$ 到最近的 $1$ 的距离（上下左右四连通）。

输入格式

$n, m$。然后 $n$ 行，每行 $m$ 个整数。

输出格式

$n$ 行，每行 $m$ 个整数，表示每个格子到最近 $1$ 的距离。

输入样例

3 3
001
100
010

输出样例

1 1 0 
0 1 1 
1 0 1

提示

• 多源BFS。所有 $1$ 同时入队，同时扩散。
• 第一次访问某 $0$ 时的距离即为答案。
• 时间复杂度 $O(nm)$。

第四层是Zero的神经脉络。无数条发光的线路在虚空中交错，但有些线路断了——断口处冒着微弱的火花。

"脉络断了。"Echo说，"Zero的意识在衰退。不是因为我们在攻击它，是因为它自己内部在腐烂。"

"那我们要修？"CC问。

"不。"你说，"我们要找到从入口到核心、需要翻转最少线路的路径。"

"翻转？"

"有些线路方向反了。"你指着一条断口，"翻过来就能连通，但每翻一条都要付出代价。"

"这就像……"CC说，"在烂掉的血管里找一条最通畅的路。"

"对。"