Cod sursa(job #2556252)

Utilizator PatriciaCretoiuCretoiu Patricia PatriciaCretoiu Data 24 februarie 2020 19:38:49
Problema Barbar Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("barbar.in");
ofstream out("barbar.out");
int dx[]= {-1, 0, 1, 0};
int dy[]= {0, 1, 0, -1};
const int N = 1005;
int n, m, i, j, xi, yi, xf, yf, ans;
int a[N][N], aLee[N][N], d[N][N];
queue<pair<int,int>>q;
char x;

bool ok(int x, int y)
{
    if(x<1 || y<1 || x>n || y>m)
        return 0;
    if(a[x][y] == -1)
        return 0;
    return 1;
}

void LeeDragoni()
{
    while(!q.empty())
    {
        int ipos = q.front().first;
        int jpos = q.front().second;
        q.pop();
        for(int i=0; i<4; i++)
        {
            int lin = ipos + dx[i];
            int col = jpos + dy[i];
            if(ok(lin,col) && (aLee[lin][col]>aLee[ipos][jpos]+1 || aLee[lin][col]==0))
            {
                aLee[lin][col] = aLee[ipos][jpos] + 1;
                q.push(make_pair(lin,col));
            }
        }
    }
}

int verif(int dist)
{
    while(!q.empty())
        q.pop();

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            d[i][j] = 0;

    q.push(make_pair(xi, yi));
    d[xi][yi] = 1;

    while(!q.empty())
    {
        int ipos = q.front().first;
        int jpos = q.front().second;
        q.pop();
        for(int i=0; i<4; i++)
        {
            int lin = ipos + dx[i];
            int col = jpos + dy[i];
            if(ok(lin,col) && aLee[lin][col]>=dist && (d[lin][col]>d[ipos][jpos]+1 || d[lin][col] == 0))
            {
                if(lin == xf && col == yf) return 1;
                d[lin][col] = d[ipos][jpos] + 1;
                q.push(make_pair(lin,col));
            }
        }
    }
    return 0;
}

void CautBin(int st, int dr)
{
    while(st <= dr)
    {
        int mij = (st + dr)/2;
        if(verif(mij) == 1)
        {
            ans = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
}

int main()
{
    in >> n >> m;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            in >> x;
            if(x == '*') a[i][j] = -1;
            else if(x == 'D') a[i][j] = -1, q.push(make_pair(i,j));
            else if(x == 'I') xi = i, yi = j;
            else if(x == 'O') xf = i, yf = j;
        }

    LeeDragoni();

    CautBin(0, n*m);

    if(ans == 0) out << -1;
    else out << ans;

    return 0;
}