矩阵距离

参考

复习BFS

参考代码

思路

直接的思路是对每个值为 0 的点进行BFS，找到其最近（曼哈顿距离）的且值为 1 的点的距离。但是这样的时间复杂度（最坏）很可能达到 $O(n^4)$ 。

因此采用多源 BFS 算法，把整个数组所有的值为 1 的点放入队列跑 BFS 即可。

代码

#include<iostream>
#include<cstring>

using namespace std;
const int N=1010;
typedef pair<int,int>PII;
char g[N][N];
int dist[N][N];
int hh=0,tt=-1;
PII q[N*N];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int n,m;
bool check(int a,int b){
    return (a>=1 and a<=n and b>=1 and b<=m);
}
void bfs(){
    while(hh<=tt){
        auto t=q[hh++];
        for(int i=0;i<4;i++){
            int a=t.first+dx[i],b=t.second+dy[i];
            if(not check(a,b))continue;
            if(dist[a][b]>=0)continue;
            q[++tt]={a,b};
            dist[a][b]=dist[t.first][t.second]+1;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
            if((g[i][j]-'0')==1){
                dist[i][j]=0;
                q[++tt]={i,j};
            }
            else{
                dist[i][j]=-1;
            }
        }
    }
    bfs();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<dist[i][j]<<" ";
        }
        cout<<endl;
    }
}