算法提高之矩阵距离

算法提高之矩阵距离

• 核心思想：多源bfs

  • 从多个源头做bfs，求距离

  • 

  • 先把所有1的坐标存入队列 再把所有1连接的位置存入 一层一层求

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 1010;
    #define x first
    #define y second
    typedef pair<int, int> PII;
    
    int dist[N][N];
    int n,m;
    int hh,tt=-1;
    char g[N][N];
    PII p[N*N];
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    void bfs()
    {
        memset(dist,-1,sizeof dist);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(g[i][j] == '1')  //把所有1的位置放入
                {
                     p[++tt] = {i,j};
                     dist[i][j] = 0;  //距离初始化为0
                }
                
        while(hh<=tt)
        {
            auto t = p[hh++];
            for(int i=0;i<4;i++)
            {
                int x = t.x+dx[i],y = t.y+dy[i];
                if(x<0 || x>=n || y<0 || y>= m || dist[x][y] != -1) continue;
                dist[x][y] = dist[t.x][t.y] + 1;
                p[++tt] = {x,y};
            }
        }
    }
    int main()
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
            cin>>g[i];
                
        bfs();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                cout<<dist[i][j]<<" ";
            cout<<endl;
        }
    }