这题最朴素暴力的方法就是对每个点做一次搜索，代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1}; 
int n,m,st[N][N];
char g[N][N];
void init()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)   
            st[i][j]=1e9;
}
void BFS(int sx,int sy)
{
    st[sx][sy]=0;
    queue<int> q1,q2;
    q1.push(sx);q2.push(sy);
    while(!q1.empty())
    {
        int x=q1.front(),y=q2.front();
        q1.pop(),q2.pop();
        for(int i=0;i<4;i++)
        {
            int tx=x+dx[i],ty=y+dy[i];
            if(tx>=1 and tx<=n and ty>=1 and ty<=m and st[x][y]+1<=st[tx][ty] and g[tx][ty]!='1')
            {
                st[tx][ty]=st[x][y]+1;
                q1.push(tx);
                q2.push(ty);
            }   
        } 
    } 
}
int main()
{
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=n;i++)
        scanf("%s",g[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(g[i][j]=='1')
                BFS(i,j);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d ",st[i][j]);
        printf("\n");
    }   
    return 0;
}

然后不出所料的TLE了

那么怎么办呢？就是把每一个是 “1” 的点都入队，之后挨个进行搜索即可。

这个比较好理解，不懂可以看yxc的讲解：link

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
int dist[N][N],n,m;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
void BFS()
{
    queue<int> q1,q2;
    memset(dist,-1,sizeof dist);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(g[i][j]=='1')
            {
                dist[i][j]=0;
                q1.push(i),q2.push(j); 
            }
    while(!q1.empty())
    {
        int x=q1.front(),y=q2.front();
        q1.pop(),q2.pop();
        for(int i=0;i<4;i++)
        {
            int tx=x+dx[i],ty=y+dy[i];
            if(tx>=1 and tx<=n and ty>=1 and ty<=m and dist[tx][ty]==-1)
            {
                dist[tx][ty]=dist[x][y]+1;
                q1.push(tx),q2.push(ty);    
            } 
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    BFS();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<<dist[i][j]<<" ";
        printf("\n");
    } 
    return 0;
}