题目描述

略

思路

最开始我用的暴力枚举，轻轻松松超时
然后用的单源BFS，也超时了（其实时间复杂度跟暴力枚举差不多）
最后用的多源BFS（可能我的代码会比较好理解一些）
在理解这个算法的时候可以联想一下那种“扩散”的题目，每走一步，1就把周围的0变成了1，然后这样扩散出去，距离就是在扩散的上一个位置的距离+1，因为是广度优先，所以只要该位置上的距离有效，就一定是最短距离，所以之后就不再考虑该位置了

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<math.h>
using namespace std;
const int N=1000+10;
int n,m;
int xi[4]={0,0,-1,1};//标记走的方向
int yi[4]={1,-1,0,0};
int a[N][N],d[N][N];//原来的矩阵，距离
bool b[N][N];//标记走没走过
struct Node{
    int x,y;
};

queue<Node> q;

void bfs(){
    while(!q.empty()){//如果队列非空
        Node h=q.front();
        q.pop();//先取后删

        for(int i=0;i<4;i++){//4个方向
            int x1 = h.x+xi[i];//注意这里是h.x
            int y1 = h.y+yi[i];
            if(x1>=0 && y1>=0 &&x1<n&&y1<m&& !b[x1][y1] ){//位置合法&没有扩散到
                b[x1][y1]=true;//标记已经有距离了
                q.push({x1,y1});//入队，相当于扩散0变成了1
                d[x1][y1]=d[h.x][h.y]+1;//求距离
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        char line[N];
        scanf("%s",line);
        for(int j=0;j<m;j++){
            a[i][j]=line[j]-'0';
            if(a[i][j]==1){
                q.push({i,j});
                b[i][j]=true;
            }
        }
    }
    bfs();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<d[i][j]<<" ";
        }
        cout<<endl;
    }
}