洛谷P1256 显示图像

广搜练手题
题目链接

思路

打印每个数与其最近的$1$的曼哈顿距离，显然广搜，存储每一个$1$，针对每一个$1$开始广搜，逐层更新，每轮后更新的为两轮之中的最小曼哈顿距离

ACcode

#include<bits/stdc++.h>using namespace std;int n, m, a[185][185];
char v[185][185];
bool f[185][185];struct node {int x, y, d;
};
queue<node>q;int xx[4] = { 0,0,1,-1 };
int yy[4] = { 1,-1,0,0 };void bfs() {node now, nex;while (!q.empty()) {now = q.front();q.pop();int x = now.x;int y = now.y;int d = now.d;a[x][y] = d;for (int i = 0;i < 4;i++) {int nx = x + xx[i];int ny = y + yy[i];if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !f[nx][ny] && v[nx][ny] == '0') {f[nx][ny] = 1;nex.x = nx;nex.y = ny;nex.d = d + 1;q.push(nex);}}}
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;memset(f, 0, sizeof f);node op;for (int i = 1;i <= n;i++) {for (int j = 1;j <= m;j++) {cin >> v[i][j];if (v[i][j] == '1') {op.x = i;op.y = j;op.d = 0;q.push(op);}}}bfs();for (int i = 1;i <= n;i++) {for (int j = 1;j <= m;j++) {cout << a[i][j] << ' ';}cout << '\n';}
}