1 solutions

  • 0
    @ 2024-8-1 9:47:25
    #include<bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> PII;
    #define x first
    #define y second 
    int n,m;
    const int N=1010;
    int dist[N][N];
    char g[N][N];
    int dx[]={-1,1,0,0};
    int dy[]={0,0,-1,1};
    void bfs()
    {
        queue<PII> q;
        memset(dist,0x3f,sizeof dist);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(g[i][j]=='1')
                {
                    q.push({i,j});
                    dist[i][j]=0;
                }
            }
        }
        while(q.size())
        {
            PII t=q.front();
            q.pop();
            for(int i=0;i<4;i++)
            {
                int a=t.x+dx[i],b=t.y+dy[i];
                if(a<0||a>=n||b<0||b>=m) continue;
                if(g[a][b]=='1') continue;
                if(dist[a][b]!=0x3f3f3f3f) continue;
                dist[a][b]=dist[t.x][t.y]+1;
                q.push({a,b});  
            } 
        }
    }
    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;
        }
        return 0;
    }
    
    • 1

    Information

    ID
    228
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    26
    Accepted
    7
    Uploaded By