原题链接： https://www.acwing.com/problem/content/description/175/

题目描述

给定一个N行M列的01矩阵A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为： dist(A[i][j],A[k][l])=|i−k|+|j−l| 输出一个N行M列的整数矩阵B，其中： B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y]) 输入格式 第一行两个整数n,m。 接下来一个N行M列的01矩阵，数字之间没有空格。 输出格式 一个N行M列的矩阵B，相邻两个整数之间用一个空格隔开。 数据范围 1≤N,M≤1000 输入样例： 3 4 0001 0011 0110 输出样例： 3 2 1 0 2 1 0 0 1 0 0 1

题解

将多个源点加入队列中，然后按照一般BFS即可

#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1010; typedef pair<int, int> PII; char g[N][N]; int n, m; int dist[N][N]; PII q[N*N]; void bfs() { memset(dist, -1, sizeof dist); int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; int hh = 0, tt = -1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(g[i][j] == '1') { q[++tt] = {i, j}; dist[i][j] = 0; } } } while(hh <= tt) { auto t = q[hh++]; int x = t.first, y = t.second; for(int k = 0; k < 4; k++) { int a = x + dx[k], b = y + dy[k]; if(a <= 0 || a > n || b <= 0 || b > m || dist[a][b] != -1) continue; dist[a][b] = dist[x][y] + 1; q[++tt] = {a, b}; } } } int main() { cin >> n >> m; for(int i = 1; i <= n; i++) scanf("%s", g[i] + 1); bfs(); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cout << dist[i][j] << " "; } puts(" "); } return 0; }