题目描述

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

算法1

(多源bfs) $O(n^2)$

因为0到1的距离就是1到0的距离，比较暴力的想法是对每个1跑一下bfs，但是显然会超时，多源BFS能很好的解决这个问题，因为如果我们把所有源点加入队列后，跑出来的路径距离依然是最短路，因为对于每个源点派生出来的分支，只在每一层上遍历的顺序不同，对于不同深度（即距离），也是遵循从上至下，所以跑出来的距离依然是最短路~。~

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

#define pii pair<int,int>

using namespace std;

const int N = 1010 , M = N*N;

int n,m;

char g[N][N];

int dist[N][N];

pii q[M];

int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
void bfs(){

    memset(dist,-1,sizeof dist);

    int tt=-1,hh=0;

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='1')
            {
                dist[i][j]=0;
                q[++tt]={i,j};
            }
        }

    while(tt>=hh)
    {
        pii t=q[hh++];

        for(int i=0;i<4;i++)
        {
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a>=0&&a<n&&b>=0&&b<m&&dist[a][b]==-1)
            {
                dist[a][b]=dist[t.first][t.second]+1;
                q[++tt]={a,b};
            }
        }
    }

}

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

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

    for(int i=0;i<n;i++) scanf("%s",g[i]);

    bfs();

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cout << dist[i][j] << " ";
        puts("");
    }

    return 0;
}