Cod sursa(job #2940395)

Utilizator tmi26Teodor Stupariu tmi26 Data 15 noiembrie 2022 14:33:14
Problema Barbar Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>

using namespace std;
int mat[1005][1005];
int din[1005][1005];
int ver[1005][1005];
int f[1005][1005];
pair<int,int> dir[4]= {{-1,0},{0,1},{1,0},{0,-1}};
deque <pair<int,int>> d;
void mubfs()
{
    while(d.size())
    {
        int i,j;
        tie(i,j)=d.back();
        for(int k=0;k<4;k++)
        {
            int x=i+dir[k].first,y=j+dir[k].second;
            if(!f[x][y])
            d.push_back({x,y});

        }
    }
}
int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            char ch;
            cin>>ch;
            if(ch=='*')
                mat[i][j]=1;
            d.push_back((i-1)*m+j);
        }
    }
    mubfs();
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            int minn=1e9;
            for(int l=0;l<4;l++)
            {
                int x=dir[l].first+i,y=dir[l].second+j;
                if(!mat[x][y])
                    minn=min(minn,din[x][y]);
            }
            din[i][j]=minn+ver[i][j];
        }
    }
    return 0;
}