这道题要求对于地图上的每个位置,求它到最近字符 ′0′ 的最少步数。每次只能向上、下、左、右走一步,因此本质上是在网格图上求每个点到最近多个起点的最短路。
这里使用的相关算法是多源广度优先搜索,也就是多源 BFS。
核心思路如下:
先把所有值为 ′0′ 的位置同时加入队列,并把这些位置的距离初始化为 0。因为这些点本身就是目标点,所以它们到最近 ′0′ 的距离就是 0。
给定一张由 n 行、m 列组成的地图。用字符,′0′ 表示天才同学的别墅位置,用字符 ′1′,表示其他位置对于地图上的每一个位置,定义其到最近别墅的距离为:从该位置出发,每次可以向上、下、左、右四个方向走一步(曼哈顿距离的一步),到达任意一个,′0′ 所需要的最少步数。若该位置本身就是,′0′,则距离为 0 。
在一行上输入两个整数 n,m(1≤n,m≤103) ,表示地图的行数与列数此后 n 行,每行输入一个长度为 m 的字符串 si,仅由字符,′0′ 和 ′1′,组成。保证至少存在一个位置为 ′0′。
输出 n 行。第 i 行输出 m 个整数,分别表示第 i 行每个位置到最近 ′0′ 的最短步数。相邻整数之间使用一个空格分隔。
输入
3 4
0111
0011
1111
输出
0 1 2 3
0 0 1 2
1 1 2 3
说明
对于样例中第 1 行第 1 列位置是 ′0′,因此距离为 0 ;第 1 行第 4 列到最近 ′0′ 的最短路径长度为 3 (一种方法是向左走三步)。