Cod sursa(job #1647136)

Utilizator BrandonChris Luntraru Brandon Data 10 martie 2016 19:08:12
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

class Point {
public:
    int x, y;
};

Point rom, jul;
queue <Point> q;

int n, m, R_dist[105][105], J_dist[105][105];
int dir[8][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1} };
bool mat[101][101];
char ch;

void bordare() {
    for(int i = 0; i <= n+1; ++i) {
        mat[i][0] = 1;
        mat[i][m+1] = 1;
    }

    for(int j = 0; j <= m+1; ++j) {
        mat[0][j] = 1;
        mat[n+1][j] = 1;
    }
}

void lee_R() {
    ///Initializare coada
    q.push(rom);
    R_dist[rom.x][rom.y] = 1;

    while(!q.empty()) {
        Point first = q.front();
        q.pop();

        for(int i = 0; i < 8; ++i) { ///Parcurgere directii
            Point next;
            next.x = first.x + dir[i][0];
            next.y = first.y + dir[i][1];

            if(mat[next.x][next.y]) { ///Obstacol
                continue;
            }

            if(!R_dist[next.x][next.y]) { ///Nu a trecut pe aici (e clar ca pe unde trece prima oara o sa fie valoarea mai mica decat ar fi fost la alta trecere)
                R_dist[next.x][next.y] = R_dist[first.x][first.y] + 1;
                q.push(next);
            }
        }
    }
}

void lee_J() {
    ///Initializare coada - o sa fie goala cand ajungi aici din cauza cond. de while din lee_R
    q.push(jul);
    J_dist[jul.x][jul.y] = 1;

    while(!q.empty()) {
        Point first = q.front();
        q.pop();

        for(int i = 0; i < 8; ++i) {
            Point next;
            next.x = first.x + dir[i][0];
            next.y = first.y + dir[i][1];

            if(mat[next.x][next.y]) { ///Obstacol
                continue;
            }

            if(!J_dist[next.x][next.y]) { ///Nu a trecut pe aici
                J_dist[next.x][next.y] = J_dist[first.x][first.y] + 1;
                q.push(next);
            }
        }
    }
}

int main() {
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);

    scanf("%d%d\n", &n, &m);

    for(int i = 1; i <= n; ++i) {
        char str[105];
        gets(str);
        int str_sz = strlen(str);

        for(int j = 1; j <= str_sz; ++j) {
            if(str[j - 1] == 'X') {
                mat[i][j] = 1;
            }
            else if(str[j - 1] == 'R') {
                rom.x = i;
                rom.y = j;
            }
            else if(str[j - 1] == 'J') {
                jul.x = i;
                jul.y = j;
            }
        }
    }

    bordare();
    ///Puteam sa dau vectorul ca parametru dar am preferat sa fac 2 leeuri separate idk de ce
    lee_R();
    lee_J();
    int ans = 0x3f3f3f3f; /// Un miliard si ceva... iti explic de ce am pus asa
    Point ans_coord;

    for(int i = 1; i <= n; ++i) {///Cea mai mica valoare a maximului dintre fiecare casuta din J_dist si R_dist va fi raspunsul
        for(int j = 1; j <= m; ++j) {
            int candidate = max(R_dist[i][j], J_dist[i][j]);

            if(candidate and candidate < ans) {///Tb sa fie != 0 pentru a evita obstacolele
                ans_coord.x = i;
                ans_coord.y = j;
                ans = candidate;
            }
        }
    }

    printf("%d %d %d\n", ans_coord.x, ans_coord.y, ans - 1);///-1 pt ca am cons pozitia de plecare la distanta 1
    return 0;
}