Cod sursa(job #2952056)

Utilizator Vlad_NistorNIstor Vlad Vlad_Nistor Data 8 decembrie 2022 09:55:50
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <bits/stdc++.h>
using namespace std;


int dx[] = { 1, 1, 1,-1,-1,-1, 0, 0};
int dy[] = { 0, 1,-1, 0, 1,-1, 1,-1};
char c[150][150];
int l1[150][150];
int l2[150][150];
int main(void){
    ofstream cout("rj.out");
    ifstream cin("rj.in");
    int n,m;
    pair<int,int> J, R;
    cin >> n >> m;
    string yay;
    cin.ignore();
    for(int i = 1;i<=n;i++){
        getline(cin,yay);
       // cout << yay << '\n';
        for(int j = 1;j<=m;j++){
            c[i][j] = yay[j-1];

            if(c[i][j] == 'J'){
                J.first = i;
                J.second = j;
            }else if(c[i][j] == 'R'){
                R.first = i;
                R.second = j;
            }
        }
        //cin.get(xxx);
        //cout << xxx;
    }
   /// cout << "here";
    l1[J.first][J.second] = 1;
    queue<pair<int,int>> coada;
    coada.push(J);
    /// facem intai lee pentru julieta (doamnele primele)
    while(!coada.empty()){
        int i = coada.front().first;
        int j = coada.front().second;
        coada.pop();
        for(int d = 0;d<8;d++){
            int iv = i + dx[d];
            int jv = j + dy[d];
            if(iv >= 1 && jv >= 1 && iv <= n && jv <= m && c[iv][jv] != 'X' && l1[iv][jv] == 0){
                coada.push({iv,jv});
                l1[iv][jv] = l1[i][j] + 1;
            }
        }
    }
    /// apoi facem pentru gentelman ul romeo
    l2[R.first][R.second] = 1;
    coada.push(R);
     while(!coada.empty()){
        int i = coada.front().first;
        int j = coada.front().second;
        coada.pop();
        for(int d = 0;d<8;d++){
            int iv = i + dx[d];
            int jv = j + dy[d];
            if(iv >= 1 && jv >= 1 && iv <= n && jv <= m && c[iv][jv] != 'X' && l2[iv][jv] == 0){
                coada.push({iv,jv});
                l2[iv][jv] = l2[i][j] + 1;
            }
        }
    }
    int minim = 1e5, cx = 0,cy = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(l1[i][j] == l2[i][j]&& l1[i][j] != 0){
                if(minim > l1[i][j]){
                    minim = l1[i][j];
                    cx = i;
                    cy = j;
                }
            }
        }
    }
    /*
    for(int i = 1;i<=n;i++){
        for(int j =1;j<=m;j++){
            cout << l2[i][j] << ' ';
        }
        cout << endl;
    }
    */

    cout << minim << ' ' << cx << ' ' << cy;
}