题解 | #矩阵距离 I#

多源BFS

求我选定多个点到其余点的最短距离

我们可以这么想，有一个虚拟源点，虚拟源点可以到选定的点

因为bfs走法我们可以想想成一层一层也就是越先到的肯定越小，代码实现上我们直接间将选定点入队然后就是bfs的板子就🆗

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int n,m;
char s[N][N];
int ans[N][N];
bool st[N][N];
struct node{
    int x,y,step;;
};
queue<node>q;
void bfs()
{
   int nex[4]={0,0,1,-1};
   int ney[4]={1,-1,0,0};
    while(!q.empty())
    {
        node sk = q.front();
        q.pop();
        int x = sk.x;
        int y = sk.y;
        for(int i = 0; i < 4; i++)
        {
            int xx = x + nex[i];
            int yy = y + ney[i];
            if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
            else if( st[xx][yy] == true) continue;
            ans[xx][yy] = sk.step + 1;
            st[xx][yy] = true;
            q.push({xx,yy,ans[xx][yy]});
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin>>s[i][j];
            if(s[i][j] == '1')
            {
                st[i][j] = true;
                q.push({i,j});
            }
        }
    }
    bfs();
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cout<<ans[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}