Cod sursa(job #2552332)

Utilizator bl1nk3rFilip Corlan bl1nk3r Data 20 februarie 2020 19:24:42
Problema Barbar Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>

using namespace std;

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

struct Node {
    unsigned short x, y;
};

const char dx[] = {1, 0, -1, 0};
const char dy[] = {0, 1, 0, -1};

int n, m;
Node barbar, iesire;

char mat[1002][1002];
int dist[1002][1002];
bool vst[1002][1002];

bool can_walk(int range) {
    memset(vst, 0, 1002 * 1002);

    queue<Node> que;

    if (dist[barbar.y][barbar.x] < range)
        return false;

    que.push(barbar);

    while (que.size()) {
        Node a = que.front();
        que.pop();

        for (int i = 0; i < 4; i++) {
            int cx = a.x + dx[i];
            int cy = a.y + dy[i];

            if (vst[cy][cx] || dist[cy][cx] < range) continue;

            vst[cy][cx] = true;
            que.push({cx, cy});
        }
    }

    return vst[iesire.y][iesire.x];
}

int main() {
    in >> n >> m;

    queue<Node> que;

    for (int i = 1; i <= n; i++) {
        in >> (mat[i] + 1);

        for (int j = 1; j <= m; j++) {
            switch(mat[i][j]) {
                case 'D':
                    que.push({j, i});
                    break;
                case 'I':
                    barbar = {j, i};
                    break;
                case 'O':
                    iesire = {j, i};
                    break;
            }
        }
    }

    for (int i = 0; i <= n + 1; i++) {
        dist[i][0] = dist[i][m + 1] = -1;
    }

    for (int j = 0; j <= m + 1; j++) {
        dist[0][j] = dist[n + 1][j] = -1;
    }
/*
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << mat[i][j] << " ";
        }
        cout << "\n";
    }
*/
    while (que.size()) {
        Node a = que.front();
        que.pop();

        for (int i = 0; i < 4; i++) {
            int cx = a.x + dx[i];
            int cy = a.y + dy[i];

            if (mat[cy][cx] == '*'
             || mat[cy][cx] == 'D'
             || dist[cy][cx] != 0)
                continue;

            dist[cy][cx] = dist[a.y][a.x] + 1;
            que.push({cx, cy});
        }
    }
/*
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << dist[i][j] << " ";
        }
        cout << "\n";
    } */

    int low = 0;
    int high = n * m - 1;

    int ans;

    while (low <= high) {
        int mid = (high + low) / 2;

        if (can_walk(mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }

//        cout << high << " " << low << "\n";
    }
//  1 1 1 1 1 1 0 0 0 0

    if (ans == 0) ans = -1;

    out << ans;

    return 0;
}