Cod sursa(job #2309268)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 28 decembrie 2018 19:11:38
Problema Barbar Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <bits/stdc++.h>



using namespace std;



int n, m;

pair<int, int> b, e;



queue< pair<int, int> > q;

int mp[1005][1005];

bool a[1005][1005];



const int sj[] = {0, -1, 0, 1};

const int sd[] = {-1, 0, 1, 0};



void lee(void)

{

    int i;

    pair<int, int> tp, auxp;

    while(!q.empty())

    {

        tp = q.front();

        q.pop();

        for(i = 0; i < 4; ++i)

        {

            auxp.first = tp.first + sj[i];

            auxp.second = tp.second + sd[i];

            if(mp[auxp.first][auxp.second] == 0)

            {

                mp[auxp.first][auxp.second] = mp[tp.first][tp.second] + 1;

                q.push(auxp);

            }

        }

    }

}



void clear_table()

{

    int i, j;

    for(i = 1; i <= n; ++i)

        for(j = 1; j <= m; ++j)

            a[i][j] = true;

}



bool tryfill(int i, int j, int& val)

{

    if(mp[i][j] > val && a[i][j])

    {

        a[i][j] = false;

        return ((i == e.first && j == e.second) ||

                tryfill(i, j-1, val) || tryfill(i, j+1, val) ||

                tryfill(i-1, j, val) || tryfill(i+1, j, val));

    }

    return false;

}



int bsrc(int& n, int& m)

{

    int stanga = 1, dreapta = n+m+2, med;

    while(stanga <= dreapta)

    {

        clear_table();

        med = (stanga + dreapta) / 2;

        if(tryfill(b.first, b.second, med))

            stanga = med + 1;

        else

            dreapta = med - 1;

    }

    return (stanga+dreapta) / 2;

}



int main()

{

    char c;

    int i, j;



    ifstream fin("barbar.in");

    ofstream fout("barbar.out");



    fin >> n >> m;



    for(i = 1; i <= n; ++i)

    {

        fin.get();

        for(j = 1; j <= m; ++j)

        {

            fin.get(c);

            if(c == 'I')

            {

                b.first = i;

                b.second = j;

            }

            else if(c == 'O')

            {

                e.first = i;

                e.second = j;

            }

            else if(c == 'D')

            {

                mp[i][j] = 1;

                q.push(make_pair(i, j));

            }

            else if(c == '*')

            {

                mp[i][j] = -1;

            }

        }

    }



    for(i = 0; i <= n+1; ++i)

        mp[i][0] = mp[i][m+1] = -1;

    for(i = 0; i <= m+1; ++i)

        mp[0][i] = mp[n+1][i] = -1;





    lee();

    i = bsrc(n, m);

    if(i)

        fout << i;

    else

        fout << -1;

}