P1256 显示图像

题目描述

古老的显示屏是由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：

输出样例#1：

说明

对于30%的数据：N*M<=10000；

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

woc，一看数据，有毒吧，带有浓厚的对DFS的不友好性。

所以我们很肯定的用BFS做这道题，我们只要在搜之前把每一个是1的点放入队列里面在结构体里再加一个dis，用来记录点到点的距离，用一个ans数组，每次记录最短距离，注意初始化成极大值，否则会出不可描述的错误，然后就搜索吧。

出来吧，代码！！！

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#define INF 2147483647

using namespace std;

int n, m, ans[187][187]; char map[187][187]; bool vis[187][187];

int dx[10] = {1, 0, -1, 0};

int dy[10] = {0, 1, 0, -1};

struct node {int x, y, dis;}; queue<node> Q;

void bfs(node now) {

	while(!Q.empty()) {

		now = Q.front();

		Q.pop();

		int x = now.x, y = now.y, dis = now.dis;

		ans[x][y] = min(ans[x][y], dis);

		for(int i=0; i<4; i++) {

			int xx = dx[i]+x, yy = dy[i]+y;

			if(xx <= n&&xx > 0&&yy <= m&& yy > 0&&map[xx][yy] == '0'&&!vis[xx][yy]) {

				vis[xx][yy] = 1;

				Q.push((node) {xx, yy, dis+1});

			}

		}

	}

}

int main() {

	scanf("%d%d", &n, &m);

	for(int i=1; i<=n; i++)

		for(int j=1; j<=m; j++) {

			cin>>map[i][j];

			if(map[i][j] == '1') {Q.push((node) {i, j, 0}); vis[i][j] = 1;}

			ans[i][j] = INF;

		}

	bfs(Q.front());

	for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) printf("%d ", ans[i][j]); printf("\n");}

}

巴特西

Luogu P1256 显示图像

P1256 显示图像

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章