问题 H: 跑图

问题 H: 跑图

时间限制: 1 Sec  内存限制: 64 MB
提交: 730  解决: 161
[状态] [讨论版] [提交] [命题人:]
题目描述
跑图是RPG游戏中很烦躁的事情。玩家需要跑到距离他最近的传送点的位置。现在给你一张N × M的方格图,每个方格中数值0表示为平地,数值1表示为传送点,你的任务是输出一张 N × M 的矩阵, Matrixxy表示从 (x, y) 到距离它最近的传送点的距离。 这里的距离是曼哈顿距离,(x1, y1)→ (x2, y2) 的距离为∣x1 − x2∣ + ∣y1 − y2
输入
第一行,有两个数n,m 。接下来n行,每行m个数。
数据保证至少有一个传送点。
1 ≤ n ≤ 500 ,  1 ≤ m ≤ 500

输出

n行,每行m个数,表示某个点到离它最近的传送点的距离。
样例输入 Copy
2 3
0 0 0
1 0 1
样例输出 Copy
1 2 1
0 1 0