计算像素点到最近白色像素点的距离 - BFS算法

计算像素点到最近白色像素点的距离 - BFS算法

题目描述

古老的显示屏是由 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 矩阵的方式发出显示整个屏幕图像的命令。

由于未知的原因，显示黑色的像素点总是受显示白色的像素点的影响。并且，距离越近，影响越大。这里的距离定义如下：

设有像素点 P1(x1,y1) 和像素点 P2(x2,y2)，则它们之间的距离 D(P1,P2)=|x1-x2|+|y1-y2|。

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

输入格式

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

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

输出格式

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

解题思路

我们可以使用广度优先搜索（BFS）来解决这个问题。

1. 首先，将所有白色像素点的坐标加入队列。2. 然后从队列中依次取出每个像素点，将其周围的黑色像素点的距离更新，并将这些黑色像素点的坐标加入队列。3. 重复这个过程，直到队列为空。

C++ 代码示例cpp#include #include #include using namespace std;

vector<vector> screen;vector<vector> distance;int n, m;int dx[] = {-1, 1, 0, 0};int dy[] = {0, 0, -1, 1};

void bfs() { queue<pair<int, int>> q; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (screen[i][j] == 1) { q.push({i, j}); distance[i][j] = 0; } } }

while (!q.empty()) {        int x = q.front().first;        int y = q.front().second;        q.pop();

    for (int k = 0; k < 4; k++) {            int nx = x + dx[k];            int ny = y + dy[k];            if (nx >= 0 && nx < n && ny >= 0 && ny < m && screen[nx][ny] == 0 && distance[nx][ny] == -1) {                distance[nx][ny] = distance[x][y] + 1;                q.push({nx, ny});            }        }    }}

int main() { cin >> n >> m;

screen.resize(n, vector<int>(m));    distance.resize(n, vector<int>(m, -1));

for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            cin >> screen[i][j];        }    }

bfs();

for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            cout << distance[i][j] << ' ';        }        cout << endl;    }

return 0;}

总结

本题可以使用 BFS 算法高效地解决，代码简洁易懂。希望对您有所帮助！