Cod sursa(job #1655836)

Utilizator diana97Diana Ghinea diana97 Data 18 martie 2016 13:26:48
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;

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

const int DIR = 8;
const int NMAX = 100;
const int MMAX = 100;


int n, m;
pair <int, int> pozitie_r;
pair <int, int> pozitie_j;

char oras[NMAX + 1][MMAX + 1];
int drum_r[NMAX + 1][MMAX + 1];
int drum_j[NMAX + 1][MMAX + 1];

int d_i[] = {-1, -1, 0, 1, 1,  1,  0, -1};
int d_j[] = { 0,  1, 1, 1, 0, -1, -1, -1};

void citeste() {
    f >> n >> m;

    f.getline(oras[0], MMAX);

    for (int i = 1; i <= n; i++) {
        f.getline(oras[i] + 1, MMAX);
        for (int j = 1; j <= m; j++) {
            if (oras[i][j] == 'R') pozitie_r = make_pair(i, j);
            if (oras[i][j] == 'J') pozitie_j = make_pair(i, j);
        }
    }
}

bool e_afara(int i, int j) {
    if (i == 0 || j == 0) return true;
    if (i == n + 1 || j == m + 1) return true;

    return false;
}

void rezolva() {
    queue < pair <char, pair <int, int> > > Q;

    pair <char, pair <int, int> > p;
    char personaj;
    int i, j, i_urmator, j_urmator, timp;

    p.first = 'R';
    p.second = pozitie_r;
    Q.push(p);

    p.first = 'J';
    p.second = pozitie_j;
    Q.push(p);

    drum_r[pozitie_r.first][pozitie_r.second] = drum_j[pozitie_j.first][pozitie_j.second] = 1;

    while (!Q.empty()) {
        p = Q.front();
        Q.pop();

        personaj = p.first;
        i = p.second.first;
        j = p.second.second;

        if (personaj == 'R') timp = drum_r[i][j] + 1;
        else timp = drum_j[i][j] + 1;


        for (int d = 0; d < DIR; d++) {
            i_urmator = i + d_i[d];
            j_urmator = j + d_j[d];
            //if (personaj == 'R') cout << i_urmator << ' ' << j_urmator << ' ' << oras[i_urmator][j_urmator] << endl;

            if (e_afara(i_urmator, j_urmator)) continue;
            if (oras[i_urmator][j_urmator] == 'X') continue;

            if(personaj == 'R') {
                if (drum_r[i_urmator][j_urmator]) continue;
                if (drum_j[i_urmator][j_urmator] == timp) {
                    g << timp << ' ' << i_urmator << ' ' << j_urmator << '\n';
                    return;
                }
                drum_r[i_urmator][j_urmator] = timp;
            }
            else {
                if (drum_j[i_urmator][j_urmator]) continue;
                if (drum_r[i_urmator][j_urmator] == timp) {
                    g << timp << ' ' << i_urmator << ' ' << j_urmator << '\n';
                    return;
                }
                drum_j[i_urmator][j_urmator] = timp;
            }

            p.first = personaj;
            p.second.first = i_urmator;
            p.second.second = j_urmator;
            Q.push(p);
        }
    }
}

int main() {
    citeste();
    rezolva();
}