Cod sursa(job #3159390)

Utilizator ioanabaduIoana Badu ioanabadu Data 21 octombrie 2023 11:13:33
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.25 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <climits>
#include <stdio.h>
#define N_MAX 105

using namespace std;
fstream in ("rj.in");
ofstream out ("rj.out");
int n, m;
int julieta[N_MAX][N_MAX], romeo[N_MAX][N_MAX];
pair <int, int> startj, startr, final_coord;
int rez_timp = INT_MAX;

void input () {
    in >> n >> m;
    char aux[N_MAX];
    in.getline (aux, 2);
    for (int i=1; i<=n; i++){
        in.getline (aux, N_MAX);
        for (int k=0; k<m; k++) {
            if (aux[k] == 'X') {
                romeo[i][k+1] = -1;
                julieta[i][k+1] = -1;
            }
            else if (aux[k] == 'R') {
                startr.first = i;
                startr.second = k+1;
            }
            else if (aux[k] == 'J') {
                startj.first = i;
                startj.second = k+1;
            }
        }
    }
}

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

int lin[] = {0, -1, 0, 1, 1, -1, 1, -1}, col[] = {1, 0, -1, 0, 1, -1, -1, 1};

void lee_julieta (){
    queue <pair <int, int>> q;
    q.push ({startj.first, startj.second});
    pair <int, int> current, future;
    julieta[startj.first][startj.second] = 1;
    while (!q.empty()){
        current = q.front();
        for (int i=0; i<8; i++){
            future.first = current.first + lin[i];
            future.second = current.second + col[i];
            if (julieta[future.first][future.second] == 0) {
                julieta[future.first][future.second] = julieta[current.first][current.second] + 1;
                q.push ({future.first, future.second});
            }
        }
        q.pop();
    }

}

void lee_romeo () {
    queue <pair <int, int>> q;
    q.push ({startr.first, startr.second});
    pair <int, int> current, future;
    romeo[startr.first][startr.second] = 1;
    while (!q.empty()){
        current = q.front();
        for (int i=0; i<8; i++){
            future.first = current.first + lin[i];
            future.second = current.second + col[i];
            if (romeo[future.first][future.second] == 0) {
                romeo[future.first][future.second] = romeo[current.first][current.second] + 1;
                q.push ({future.first, future.second});
            }
        }
        q.pop();
    }
}

void solve () {
    lee_julieta ();
    lee_romeo ();
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            if (romeo[i][j] > 0 && julieta[i][j] > 0) {
                if (romeo[i][j] == julieta[i][j]){
                    cout << "BLA";
                    if (romeo[i][j] < rez_timp) {
                        rez_timp = romeo[i][j];
                        final_coord.first = i;
                        final_coord.second = j;
                    }
                }
            }
        }
    }
    out << rez_timp << ' ' << final_coord.first << ' ' << final_coord.second;
}

int main () {
    input();
    border();
    solve();
    return 0;
}