P1256 显示图像

2023-12-27 10:00:20

题目

题目描述

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

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

( 0 0 0 1 0 0 1 1 0 1 1 0 ) \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ \end{pmatrix} ?000?001?011?110? ?

对应屏幕显示应为:

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

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

设有像素点 P 1 ( x 1 , y 1 ) P_1(x_1,y_1) P1?(x1?,y1?) 和像素点 P 2 ( x 2 , y 2 ) P_2(x_2,y_2) P2?(x2?,y2?),则它们之间的距离 D ( P 1 , P 2 ) = ∣ x 1 ? x 2 ∣ + ∣ y 1 ? y 2 ∣ D(P_1,P_2)=|x_1-x_2|+|y_1-y_2| D(P1?,P2?)=x1??x2?+y1??y2?

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

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

输入格式

第一行有两个数字, N N N M ? ( 1 ≤ N , M ≤ 182 ) M\ (1 \le N,M \le 182) M?(1N,M182),表示屏幕的规格。

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

输出格式

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

样例 #1

样例输入 #1

3 4
0001
0011
0110

样例输出 #1

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

提示

  • 对于 30 % 30\% 30% 的数据: N × M ≤ 10000 N\times M \le 10000 N×M10000
  • 对于 100 % 100\% 100% 的数据: N × M ≤ 18 2 2 N\times M \le 182^2 N×M1822

我懂,你们肯定想要不带markdown格式的题目来让C知道回答

所以我把它整理出来,放这里

解题

first

观察输入

3 4
0001
0011
0110

您猜怎么着?

出题人太阴险了,中间没空格TMD害得我WA了14次。。。

    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        //读入本行的所有元素
        for(int j=0;j<s.size();j++)
        if(s[j]=='0')
        f[i][j+1]=false;
        //如果是0就标记为没有访问过,反过来说,就是把所有1都标记为访问过了
        else
        {
            d[i][j+1]=0;
            //初始化距离0;
            f[i][j+1]=true;
            //访问过啦
            a[++tail].x=i;
            a[tail].y=j+1;
            //入队
        }
    }

啊,相信很多人想要代码不想要解题过程,所以

代码放这里了

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct MAP
{
    int x,y;
}a[1000010];
//维护一个队列来记录进队顺序
bool f[1010][1010];
//标记这个点有没有被搜索过。
int d[1010][1010];
//这个点就是,用来存最短距离的,初值全部为0;
int dx[5]={0,0,0,-1,1},dy[5]={0,-1,1,0,0};
//direct!!方向数组是个小技能,学会能发挥很大的威力
int tail=0,head=0;
//队头和队尾
int main()
{
    memset(f,true,sizeof(f));
    //初始化全部标为true,访问过。
    scanf("%d%d",&n,&m);
    //读入啊
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        //读入本行的所有元素
        for(int j=0;j<s.size();j++)
        if(s[j]=='0')
        f[i][j+1]=false;
        //如果是0就标记为没有访问过,反过来说,就是把所有1都标记为访问过了
        else
        {
            d[i][j+1]=0;
            //初始化距离0;
            f[i][j+1]=true;
            //访问过啦
            a[++tail].x=i;
            a[tail].y=j+1;
            //入队
        }
    }
    //按队列顺序开始搜索
    for(head=1;head<=tail;head++)//枚举队首
    {
        for(int i=1;i<=4;i++)
        //用direct数组来向四方扩展。
        {
            int xx=a[head].x+dx[i],yy=a[head].y+dy[i];
            //方向数组的用处就在这里了
            if(!f[xx][yy])
            //如果没有被访问过
            {
                d[xx][yy]=d[a[head].x][a[head].y]+1;
                //这个点的距离=队头距离+1;
                f[xx][yy]=true;
                //标记访问过
                a[++tail].x=xx;
                a[tail].y=yy;
                //入队。
            }
        }
    }
    //d数组就是距离,现在可以输出了
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        printf("%d ",d[i][j]);
        printf("\n");
    }
    return 0;
}

相信大伙不是这样的人

话说那些想要代码不想要解题过程的人是不是该留下一个赞啊?

解题思路大概就是搜索

if(f[i][j]!=0){
	f[i][j]=min(f[i-1][j],f[i][j-1]);
}

不错

文章来源:https://blog.csdn.net/hdminn/article/details/135185211
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。