Cod sursa(job #1049495)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 7 decembrie 2013 13:29:16
Problema Barbar Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <queue>
using namespace std;

ifstream is("barbar.in");
ofstream os("barbar.out");

#define mp make_pair
#define pb push_back
typedef vector<vector<int> > VVI;
typedef vector<vector<char> > VVC;
const int INF = 0x3f3f3f3f;
const int di[] = { -1, 0, 1, 0 },
          dj[] = { 0, 1, 0, -1 };
int m, n, i1, j1, i2, j2, dmax;
VVI d;
VVC a;
queue<pair< int, int> > Q;
void Read();
void Lee();
bool Ok ( int i, int j );
void Write();
bool Check( int x );
void Solve();

int main()
{
    Read();
    Lee();
    Solve();
    is.close();
    os.close();
    return 0;
}

void Solve()
{
    int L = 1, R = dmax;
    int rez = -1;
    while ( L <= R )
    {
        int mid = ( L + R ) >> 1;
        if ( Check( mid ) )
        {
            rez = mid;
            L = mid + 1;
        }
        else    R = mid - 1;
    }
    os << rez;
}

#define iv (i + di[k])
#define jv (j + dj[k])

bool Check( int x )
{
    deque<pair<int, int>> Q;
    vector<vector<bool> > ver ( m + 1, vector<bool>( n + 1, false));
    int i = i1, j = j1;
    Q.push_back(mp(i, j) );
    while ( !Q.empty() )
    {
        i = Q.front().first, j = Q.front().second;
        Q.pop_front();
        for ( int k = 0; k < 4; k++ )
        {
            if ( Ok(iv, jv ) && ver[iv][jv] == false && d[iv][jv] >= x )
            {
                ver[iv][jv] = true, Q.push_back(mp(iv, jv));
                if ( iv == i2 && jv == j2 )
                    return true;
            }
        }
    }
     return false;
}

void Lee()
{
        while ( !Q.empty() )
        {
            int i = Q.front().first, j = Q.front().second;
            Q.pop();
            for ( int k = 0; k < 4; k++ )
            {
                if ( Ok( iv, jv ) && d[iv][jv] > d[i][j] + 1 )
                {
                    d[iv][jv] = d[i][j] + 1;
                    dmax = max(dmax, d[iv][jv]);
                    Q.push(mp(iv, jv ));
                }
            }
        }
}

bool Ok( int i, int j )
{
    if ( i < 1 || j < 1 || i > m || j > n )
        return false;
    if ( a[i][j] == '*' || a[i][j] == 'D' )
        return false;
    return true;
}

void Read()
{
    is >> m >> n;
    d = VVI( m + 1, vector< int>( n + 1, INF) );
    a = VVC( m + 1, vector< char>( n + 1) );
    for ( int i = 1; i <= m; i++ )
        for ( int j = 1; j <= n; j++ )
        {
            is >> a[i][j];
            if ( a[i][j] == 'I' )
                i1 = i, j1 = j;
            if ( a[i][j] == 'O' )
                i2 = i, j2 = j;
            if ( a[i][j] == 'D' )
               Q.push(mp(i,j)), d[i][j] = 0;
        }
}

void Write()
{
    for ( int i = 1; i <= m; i++ )
    {
        for ( int j = 1; j <= n; j++ )
            if ( d[i][j] == INF )
                os << setw(3) << "oo";
            else
                os << setw(3) << d[i][j];
        os << '\n';
    }
}