题目描述

给定一个 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

样例

blablabla

算法1

多源bfs 把每个1入队 就可将0与1的距离算出
若直接枚举每个0到最近的1的距离则时间复杂度不符合条件

blablabla

时间复杂度

参考文献

C++ 代码

#include<stdio.h>
#include<iostream>
#include<queue>
#define N 1005
using namespace std;
struct Node{
    int x;
    int y;
}node;
queue<Node>q;
int dxy[4][2]={0,1,0,-1,1,0,-1,0};
int n,m;
char map[N][N];
int dis[N][N];
bool st[N][N];
void bfs(){
    while(!q.empty()){
       node=q.front();
       q.pop();
       for(int i=0;i<4;i++){
          int xx=node.x+dxy[i][0];
          int yy=node.y+dxy[i][1];
          if(xx<0||yy<0||xx>=n||yy>=m)continue;
          if(map[xx][yy]=='0'&&!st[xx][yy]){
            dis[xx][yy]=dis[node.x][node.y]+1;
            st[xx][yy]=1;
            q.push({xx,yy});
          }
    }

    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) scanf("%s",map[i]);//注意此时不能用两种循环输入  第一次犯的错误就是这个
    for(int i=0;i<n;i++)
       for(int j=0;j<m;j++)
           if(map[i][j]=='1'&&!st[i][j]){
               q.push({i,j});
               dis[i][j]=0;
               st[i][j]=1;
           }
    bfs();   
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            printf("%d ",dis[i][j]);
        printf("\n");
    }
    return 0;
}