显示图像

题目描述

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

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

$$\begin{pmatrix}
0 & 0 & 0 & 1 \
0 & 0 & 1 & 1 \
0 & 1 & 1 & 0 \
\end{pmatrix}$$

对应屏幕显示应为：

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

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

设有像素点 $P_1(x_1,y_1)$ 和像素点 $P_2(x_2,y_2)$，则它们之间的距离 $D(P_1,P_2)=|x_1-x_2|+|y_1-y_2|$。

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
3 4
0001
0011
0110

样例输出 #1

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

提示

  • 对于 $30%$ 的数据：$N\times M \le 10000$；
  • 对于 $100%$ 的数据：$N\times M \le 182^2$。

解题思路

解题关键

以字符串数组的形式读入数据，并将数据拆分写入二维整型数组中

1
2
3
4
5
6
7
8
for(i=0;i<N;i++){
    scanf("%s",&ch[i]); //%s输入字符串
}
for(i=0;i<N;i++){
    for(j=0;j<M;j++){
        A[i][j]=ch[i][j]-48;
    }
}

主要思路

将输入为1的位置标记为0，用二维整型数组B储存遍历每一个1时所有格子应标记的值，用二维整型数组C储存最终的值，将数组B中对应位置的值与数组C中比较，若B中的值小于C中的值，则将C中的值改为B中的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
for(i=0;i<N;i++){
    for(j=0;j<M;j++){
        if(A[i][j]==1){
            for(a=0;a<N;a++){
                for(b=0;b<M;b++){
                    if(a<=i&&b<=j){
                        B[a][b]=i+j-a-b;
                    }
                    if(a>=i&&b<=j){
                        B[a][b]=a-i+j-b;
                    }
                    if(a<=i&&b>=j){
                        B[a][b]=i-a+b-j;
                    }
                    if(a>=i&&b>=j){
                        B[a][b]=a-i+b-j;
                    }
                    if(B[a][b]<C[a][b]){
                        C[a][b]=B[a][b];
                    }
                }
            }
        }
    }
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<stdio.h>
#define n 182
int main()
{
    int N,M,i,j,a,b,x,y;
    int A[n][n]={0};
    int C[n][n];
    int B[n][n]={0};
    char ch[n][n];
    scanf("%d%d",&N,&M);
    for(i=0;i<N;i++){
        scanf("%s",&ch[i]);
    }
    for(i=0;i<N;i++){
        for(j=0;j<M;j++){
            A[i][j]=ch[i][j]-48;
        }
    }
    for(i=0;i<N;i++){
        for(j=0;j<M;j++){
            if(A[i][j]==1){
                C[i][j]=0;
            }
            else{
                C[i][j]=33124;
            }
        }
    }
    for(i=0;i<N;i++){
        for(j=0;j<M;j++){
            if(A[i][j]==1){
                for(a=0;a<N;a++){
                    for(b=0;b<M;b++){
                        if(a<=i&&b<=j){
                            B[a][b]=i+j-a-b;
                        }
                        if(a>=i&&b<=j){
                            B[a][b]=a-i+j-b;
                        }
                        if(a<=i&&b>=j){
                            B[a][b]=i-a+b-j;
                        }
                        if(a>=i&&b>=j){
                            B[a][b]=a-i+b-j;
                        }
                        if(B[a][b]<C[a][b]){
                            C[a][b]=B[a][b];
                        }
                    }
                }
            }
        }
    }
    for(i=0;i<N-1;i++){
        for(j=0;j<M-1;j++){
            printf("%d ",C[i][j]);
        }
        printf("%d\n",C[i][j]);
    }
    for(j=0;j<M-1;j++){
        printf("%d ",C[i][j]);
    }
    printf("%d",C[i][j]);
    return 0;
}