Cod sursa(job #1729422)

Utilizator DastasIonescu Vlad Dastas Data 14 iulie 2016 18:02:19
Problema Barbar Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.2 kb
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;

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

int n, m, stx, sty, sfx, sfy;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int  a[1002][1002], b[1002][1002];


struct Element {
    int ab, ord;
}aux, work;

queue<Element> q;

void read() {
    char c;
    fin >> n >> m;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            fin >> c;
            if (c == 'I') {
                a[i][j] = 1 << 30;
                stx = i;
                sty = j;
            }
            else if (c == 'O') {
                a[i][j] = 1 << 30;
                sfx = i;
                sfy = j;
            }
            else if (c == 'D') {
                a[i][j] = 0;
                Element e;
                e.ab = i;
                e.ord = j;
                q.push(e);
            }
            else if (c == '*') {
                a[i][j] = -4;
            }
            else
                a[i][j] = 1 << 30;
        }
    }

    for (int i=0; i<=n+1; i++)
      a[i][0] = a[i][m+1] = -4;
    for (int j=0; j<=m+1; j++)
      a[0][j] = a[n+1][j] = -4;
}

void dragons() {
    while (!q.empty())
    {
        Element x = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            int newx = x.ab + dx[i];
            int newy = x.ord + dy[i];

            if (a[newx][newy] > a[x.ab][x.ord] + 1)
            {
                a[newx][newy] = a[x.ab][x.ord] + 1;
                Element t;
                t.ab = newx;
                t.ord = newy;
                q.push(t);
            }
        }
    }

/*    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cout << a[i][j] << '\t';
        }
        cout << endl;
    }*/
}

void copying() {
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            b[i][j] = a[i][j] >= 0 ? 1 << 30 : a[i][j];

    for (int i=0; i<=n+1; i++)
      b[i][0] = b[i][m+1] = -4;
    for (int j=0; j<=m+1; j++)
      b[0][j] = b[n+1][j] = -4;
}

int drum(int k) {
    copying();
    q = queue<Element>();
    aux.ab = stx;
    aux.ord = sty;
    b[stx][sty] = 0;
    if (a[stx][sty] < k)
        return 0;
    q.push(aux);
    while (!q.empty()) {
        aux = q.front();

        if (sfx == aux.ab && sfy == aux.ord) {
            return 1;
        }

        q.pop();
        for (int i=0; i<4; i++) {
            work.ab = aux.ab + dx[i];
            work.ord = aux.ord + dy[i];

            if (a[work.ab][work.ord] >= k && b[aux.ab][aux.ord] + 1 < b[work.ab][work.ord]) {
                q.push(work);
                b[work.ab][work.ord] = b[aux.ab][aux.ord] + 1;
            }
        }
    }
    return 0;
}

int caut (int st, int dr) {
    int mij, ras=-1;
    while (st < dr) {
        mij = (st + dr) / 2;
        if (drum(mij) == 1) {
            st = mij + 1;
            ras = mij;
        }
        else
            dr = mij;
    }
    return ras;
}

int main() {
    int big;
    read();
    big = 2 * max(n, m) - 2;
    dragons();
    fout << caut(0, big);
    return 0;
}