Cod sursa(job #3160540)

Utilizator Octa-pe-infoNechifor Octavian Octa-pe-info Data 24 octombrie 2023 16:15:22
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <fstream>
#include <queue>
using namespace std;

queue < pair<int, int> > R;
queue < pair<int, int> > J;
pair <int, int> startrom;
pair <int, int> startjul;

int romeo[102][102], julieta[103][103];
int n, m;
int di[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dj[8] = {0, 1, 1, 1, 0, -1, -1, -1};

void bordare(){
    for(int i = 0; i <= n + 1; i++) {
        romeo[i][0] = -1;
        romeo[i][m + 1] = -1;
        julieta[i][0] = -1;
        julieta[i][m + 1] = -1;
    }
    for(int j = 1; j <= m; j++) {
        romeo[0][j] = -1;
        romeo[n + 1][j] = -1;
        julieta[0][j] = -1;
        julieta[n + 1][j] = -1;
    }
}

void citire() {
    char c;

    ifstream fin("rj.in");
    fin >> n >> m;
    fin.get(c);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++){
            fin.get(c);
            if(c == 'R') {
                startrom.first = i;
                startrom.second = j;
                julieta[i][j] = 0;
            }
             if(c == 'J') {
                startjul.first = i;
                startjul.second = j;
                romeo[i][j] = 0;
            }
             if(c == ' ') {
                romeo[i][j] = 0;
                julieta[i][j] = 0;
            }
             if(c == 'X') {
                romeo[i][j] = -1;
                julieta[i][j] = -1;
            }
        }
        fin.get(c);
    }
}

void leer() {
    R.push(startrom);
    romeo[startrom.first][startrom.second] = 1;
    while(!R.empty()) {
        pair<int, int> current = R.front();
        R.pop();
        for(int k = 0; k < 8; k++) {
            int pi = current.first + di[k];
            int pj = current.second + dj[k];
            if(romeo[pi][pj] == 0) {
                romeo[pi][pj] = romeo[current.first][current.second] + 1;
                R.push({pi, pj});
            }
        }
    }
}

void leej() {
    J.push(startjul);
    julieta[startjul.first][startjul.second] = 1;
    while(!J.empty()) {
        pair<int, int> current = J.front();
        J.pop();
        for(int k = 0; k < 8; k++) {
            int pi = current.first + di[k];
            int pj = current.second + dj[k];
            if(julieta[pi][pj] == 0) {
                julieta[pi][pj] = julieta[current.first][current.second] + 1;
                J.push({pi, pj});
            }
        }
    }
}

void gasire() {
    int min_path = 200000000;
    int i_i = -1, j_j = -1, pasi = -1;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            if(romeo[i][j] == julieta[i][j] && romeo[i][j] < min_path && romeo[i][j] != 0 && romeo[i][j]!=-1) {
                pasi = romeo[i][j];
                min_path = pasi;
                i_i = i;
                j_j = j;
            }
        }

    ofstream fout("rj.out");
    if(i_i != -1 && j_j != -1 && pasi != -1) {
        fout << pasi << " " << i_i << " " << j_j;
    }
}

int main() {
    citire();
    bordare();
    leer();
    leej();
    gasire();
    return 0;
}