logo AlgoBeat OnlineJudge
登录 注册

#200254. [POI 1999 R2] 显示图像

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

古老的显示屏是由 个像素(Pixel)点组成的。一个像素点的位置是根据所在行数和列数决定的。例如 表示第 行第 列的像素点。那时候,屏幕只能显示黑与白两种颜色,人们用二进制 来表示。 表示黑色, 表示白色。当计算机发出一个指令:,则屏幕上的第 行第 列的阴极射线管就开始工作,使该像素点显示白色,若 ,则对应位置的阴极射线管不工作,像素点保持黑色。在某一单位时刻,计算机以 二维 矩阵的方式发出显示整个屏幕图像的命令。

例如,屏幕是由 的像素点组成,在某单位时刻,计算机发出如下命令:

对应屏幕显示应为:

假设放大后,一个格子表示一个像素点。

由于未知的原因,显示黑色的像素点总是受显示白色的像素点的影响——可能是阴极射线管工作的作用。并且,距离越近,影响越大。这里的距离定义如下:

设有像素点 和像素点 ,则它们之间的距离

在某一时刻,计算机发出显示命令后,科学家们期望知道,每个像素点和其最近的显示白色的像素点之间的最短距离是多少——科学家们保证屏幕上至少有一个显示白色的像素点。

上面的例子中,像素 与最近的白色像素点之间的距离为 ,而像素 本身显示白色,所以最短距离为

输入格式

第一行有两个数字,,表示屏幕的规格。

以下 行,每行 个数字,。为计算机发出的显示命令。

输出格式

输出文件有 行,每行 个数字,中间用 个空格分开。第 行第 列的数字表示距像素点 最近的白色像素点的最短距离。

样例

样例输入 1

3 4
0001
0011
0110

样例输出 1

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

数据范围与提示

  • 对于 的数据:
  • 对于 的数据: