P1256 显示图像

    • 241通过
    • 571提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 搜索
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    例如,屏幕是由3×4的 对应屏幕显示应为:

    像素点组成,在某单位时刻,

    计算机发出如下命令:

    0001 0011 0110

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

    由于未知的原因,显示黑色的像素点总是受显示白色的像素点的影响——可能是阴极射线管工作的作用。并且,距离越近,影响越大。这里的距离定义如下:设有像素点P1(x1,y1)和像素点P2(x2,y2),则它们之间的距离D(P1,P2):D(P1,P2)=|x1-x2|+|y1-y2| 在某一时刻,计算机发出显示命令后,科学家们期望知道,每个像素点和其最近的显示白色的像素点之间的最短距离是多少——科学家们保证屏幕上至少有一个显示白色的像素点。

    上面的例子中,像素P(1,1)与最近的白色像素点之间的距离为3,而像素P(3,2)本身显示白色,所以最短距离为0。

    输入输出格式

    输入格式:

    第一行有两个数字,N和M (1<=N,M<=182),表示屏幕的规格。

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    3 4
    0001
    0011
    0110
    
    输出样例#1: 复制
    3 2 1 0
    2 1 0 0
    1 0 0 1
    

    说明

    对于30%的数据:N*M<=10000;

    对于100%的数据:N*M<=182^2。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。