P1256 显示图像【洛谷算法习题】
P1256 显示图像
网页链接
P1256 显示图像
题目描述
古老的显示屏是由N × M N \times MN×M个像素（Pixel）点组成的。一个像素点的位置是根据所在行数和列数决定的。例如P ( 2 , 1 ) P(2,1)P(2,1)表示第2 22行第1 11列的像素点。那时候，屏幕只能显示黑与白两种颜色，人们用二进制0 00和1 11来表示。0 00表示黑色，1 11表示白色。当计算机发出一个指令：P ( x , y ) = 1 P(x,y)=1P(x,y)=1，则屏幕上的第x xx行第y yy列的阴极射线管就开始工作，使该像素点显示白色，若P ( x , y ) = 0 P(x,y)=0P(x,y)=0，则对应位置的阴极射线管不工作，像素点保持黑色。在某一单位时刻，计算机以N × M N \times MN×M二维01 0101矩阵的方式发出显示整个屏幕图像的命令。
例如，屏幕是由3 × 4 3 \times 43×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}000001011110
对应屏幕显示应为：
假设放大后，一个格子表示一个像素点。
由于未知的原因，显示黑色的像素点总是受显示白色的像素点的影响——可能是阴极射线管工作的作用。并且，距离越近，影响越大。这里的距离定义如下：
设有像素点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 33，而像素P ( 3 , 2 ) P(3,2)P(3,2)本身显示白色，所以最短距离为0 00。
输入格式
第一行有两个数字，N NN和M ( 1 ≤ N , M ≤ 182 ) M\ (1 \le N,M \le 182)M(1≤N,M≤182)，表示屏幕的规格。
以下N NN行，每行M MM个数字，0 00或1 11。为计算机发出的显示命令。
输出格式
输出文件有N NN行，每行M MM个数字，中间用1 11个空格分开。第i ii行第j jj列的数字表示距像素点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 10000N×M≤10000；
- 对于100 % 100\%100%的数据：N , M ≤ 182 N,M \le 182N,M≤182。
解题思路
本题核心是多源广度优先搜索(BFS)，高效求解网格中所有点到最近白色像素的最短曼哈顿距离。曼哈顿距离与网格上下左右移动的步数完全等价，多源BFS是此类问题的最优解法。首先遍历整个像素网格，将所有值为1的白色像素作为初始起点加入队列，距离设为0；随后从队列中依次取出节点，向上下左右四个方向扩展，未被访问的黑色像素距离为当前节点距离+1，标记访问状态并加入队列。BFS按层遍历的特性保证了每个点的距离都是最短值，算法时间复杂度O ( N × M ) O(N \times M)O(N×M)，完美适配题目数据规模。
总结
核心逻辑：以所有白色像素为起点进行多源BFS，同步扩散计算最短距离。
关键操作：多源起点初始化入队、四方向邻域扩展、距离赋值与访问标记。
效率保障：BFS无重复遍历，线性时间复杂度，精准计算所有点的最短距离。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,m;structMAP{ll x,y;}a[1000010];boolf[1010][1010];ll d[1010][1010];ll dx[5]={0,0,0,-1,1},dy[5]={0,-1,1,0,0};ll tail=0,head=0;intmain(){memset(f,true,sizeof(f));scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++){string s;cin>>s;for(ll j=0;j<(ll)s.size();j++)if(s[j]=='0')f[i][j+1]=false;else{d[i][j+1]=0;f[i][j+1]=true;a[++tail].x=i;a[tail].y=j+1;}}for(head=1;head<=tail;head++){for(ll i=1;i<=4;i++){ll 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;f[xx][yy]=true;a[++tail].x=xx;a[tail].y=yy;}}}for(ll i=1;i<=n;i++){for(ll j=1;j<=m;j++)printf("%lld ",d[i][j]);printf("\n");}return0;}