Cod sursa(job #2083103)

Utilizator calin9819Costea Calin calin9819 Data 7 decembrie 2017 02:52:28
Problema Barbar Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("barbar.in");
ofstream g("barbar.out");

int R, C, m[1002][1002], viz[1002][1002], q1[1000001], q2[1000001], sx, sy, dx, dy, p, u;

void bordare(int R, int C) {
    for (int i = 1; i <= R; i++)
        m[i][0] = m[i][C+1] = -1;
    for (int i = 1; i <= C; i++)
        m[0][i] = m[R+1][i] = -1;
}

void lee() {
    while (p <= u) {
        p++;
        int x = q1[p], y = q2[p];
        if (x > 1 && (m[x-1][y] == 0 || m[x][y] + 1 < m[x-1][y])) {
            u++;
            q1[u] = x - 1;
            q2[u] = y;
            m[x-1][y] = m[x][y] + 1;
        }
        if (x < R && (m[x+1][y] == 0 || m[x][y] + 1 < m[x+1][y])) {
            u++;
            q1[u] = x + 1;
            q2[u] = y;
            m[x+1][y] = m[x][y] + 1;
        }
        if (y > 1 && (m[x][y-1] == 0 || m[x][y] + 1 < m[x][y-1])) {
            u++;
            q1[u] = x;
            q2[u] = y - 1;
            m[x][y-1] = m[x][y] + 1;
        }
        if (y < C && (m[x][y+1] == 0 || m[x][y] + 1 < m[x][y+1])) {
            u++;
            q1[u] = x;
            q2[u] = y + 1;
            m[x][y+1] = m[x][y] + 1;
        }
    }
}

int test_drum(int v) {
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            viz[i][j] = 0;
    int f, l;
    f = l = 0;
    l = 1;
    q1[l] = sx;
    q2[l] = sy;
    viz[sx][sy] = 1;
    while (f <= l) {
        f++;
        int x = q1[f], y = q2[f];
        if (x > 1 && m[x-1][y] >= v && viz[x-1][y] == 0) {
            if (x-1 == dx && y == dy) return 1;
            l++;
            q1[l] = x - 1;
            q2[l] = y;
            viz[x-1][y] = 1;
        }
        if (x < R && m[x+1][y] >= v && viz[x+1][y] == 0) {
            if (x+1 == dx && y == dy) return 1;
            l++;
            q1[l] = x + 1;
            q2[l] = y;
            viz[x+1][y] = 1;
        }
        if (y > 1 && m[x][y-1] >= v && viz[x][y-1] == 0) {
            if (x == dx && y-1 == dy) return 1;
            l++;
            q1[l] = x;
            q2[l] = y - 1;
            viz[x][y-1] = 1;
        }
        if (y < C && m[x][y+1] >= v && viz[x-1][y+1] == 0) {
            if (x == dx && y+1 == dy) return 1;
            l++;
            q1[l] = x;
            q2[l] = y + 1;
            viz[x][y+1] = 1;
        }
    }
    return 0;
}

int main()
{
    f >> R >> C;
    bordare(R, C);
    for (int i = 1; i <= R; i++) {
        char c;
        for (int j = 1; j <= C; j++) {
            f >> c;
            if (c == '.') m[i][j] = 0;
            else if (c == '*') m[i][j] = -1;
            else if (c == 'I') {
                m[i][j] = 0;
                sx = i;
                sy = j;
            }
            else if (c == 'O') {
                m[i][j] = 0;
                dx = i;
                dy = j;
            }
            else if (c == 'D') {
                u++;
                q1[u] = i;
                q2[u] = j;
                m[i][j] = 1;
            }
        }

    }
    lee();

    int mini = min(m[sx][sy], m[dx][dy]);
    if (test_drum(mini)) {
        g << mini-1;
        return 0;
    }

    int st = 2, dr = mini, mid = 2;
    while (st < dr) {
        mid = (st+dr)/2;
        if (test_drum(mid)) st = mid + 1;
        else dr = mid;
    }
    g << mid-1;
    return 0;
}