Cod sursa(job #3157191)

Utilizator AlexanderCernyCernaianu Alexandru AlexanderCerny Data 14 octombrie 2023 16:39:07
Problema Barbar Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <queue>
#include <climits>
#include <cstring>

using namespace std;

ifstream fin ("barbar.in");
ofstream fout("barbar.out");

int n,m,i,j,ii,ji,io,jo;
char ch;
int a[1002][1002];
struct coada
{
    int lin;
    int col;
};
int d[1002][1002];
int dx[]={0, -1 ,0 ,1, 0}, dy[]={0, 0, 1, 0, -1};
bool viz[1002][1002];
queue<coada>q;
int bfs(int dis)
{
    while(!q.empty())
        q.pop();
    if(d[ii][ji]<=dis)
        return 0;
    memset(viz,0, sizeof(viz));
    q.push({ii,ji});
    viz[ii][ji]=1;
    while(!q.empty())
    {
        int l=q.front().lin,c=q.front().col;
        for(int i=1;i<=4;i++)
        {
            int lv=l+dx[i],cv=c+dy[i];
            if(viz[lv][cv]==0&&lv>=1&&lv<=n&&cv>=1&&cv<=m&&d[lv][cv]>dis)
            {
                q.push({lv,cv});
                viz[lv][cv]=1;
                if(lv==io&&cv==jo)
                    return 1;
            }
        }
        q.pop();
    }
    return 0;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            fin>>ch;
            if(ch=='I')
            {
                ii=i;
                ji=j;
            }
            else if(ch=='O')
            {
                io=i;
                jo=j;
            }
            else if(ch=='D')
            {
                q.push({i,j});
                d[i][j]=1;
            }
            else if(ch=='*')
                    a[i][j]=-1;
        }
    while(!q.empty())
    {
        int l=q.front().lin,c=q.front().col;
        for(i=1;i<=4;i++)
        {
            int lv=l+dx[i],cv=c+dy[i];
            if(d[lv][cv]==0&&lv>=1&&lv<=n&&cv>=1&&cv<=m&&a[lv][cv]==0)
            {
                q.push({lv,cv});
                d[lv][cv]=d[l][c]+1;
            }
        }
        q.pop();
    }
    int st=0,dr=n*m,sol=-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(bfs(mid)==1)
        {
            sol=mid;
            st=mid+1;
        }
        else
            dr=mid-1;
    }
    fout<<sol;
    return 0;
}