提示: 欢迎访问OurACM平台。
Problem 1408 位图

Accept: 512    Submit: 2358
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

现在我们给出一个n*m的黑白位图,n为行数,m为列数,且该位图中至少含有一个白色的像素。我们用(i,j)来表示第i行第j列的像素,并且定义两像素点p1=(i1,j1)和p2=(i2,j2)之间的距离为:d(p1,p2)=|i1-i2|+|j1-j2|。

对于任意给定的位图,计算出位图中每个像素到与它最近的白色像素之间的距离。

Input

本题有多组输入数据,每组数据第一行包含两个整数n,m,用空格分开,1<=n,m<=182。之后的n行每行包含一个长度为m的由0和1组成的字符串,即第i行第j个字符如果为"1",那么表示像素(i,j)为白的,否则为黑的。

Output

对于每组数据,输出包含n行,第i行的第j个数字为f(i,j),表示像素(i,j)到最近的白色像素的距离。每行内的数字用空格分开。

Sample Input

3 4 0001 0011 0110

Sample Output

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

Source

FZUPC 2006

Submit  Back  Status  Discuss