Cod sursa(job #3269689)

Utilizator stefan0211Tacu Darius Stefan stefan0211 Data 20 ianuarie 2025 14:47:39
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3 kb
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");
int n, m;
vector<vector<char>> matrice;
pair<int, int> romeo, julieta;
vector<vector<bool>> viz_r, viz_j;
vector<vector<int>> d_r, d_j;

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

    matrice.resize(n + 1, vector<char>(m + 1));
    viz_r.resize(n + 1, vector<bool>(n + 1, false));
    viz_j.resize(n + 1, vector<bool>(n + 1, false));
    viz_j.resize(n + 1, vector<bool>(n + 1, false));
    d_r.resize(n + 1, vector(n + 1, 0));
    d_j.resize(n + 1, vector(n + 1, 0));

    string s;
    getline(f, s, '\n');

    for (int i = 1; i <= n; i++)
    {

        getline(f, s, '\n');
        for (int j = 1; j <= m; j++)
        {
            matrice[i][j] = s[j - 1];
            if (matrice[i][j] == 'R')
                romeo = make_pair(i, j);
            if (matrice[i][j] == 'J')
                julieta = make_pair(i, j);
        }
    }
}

void get_vecini(vector<pair<int, int>> &v, pair<int, int> punct)
{
    int dx[] = {-1, 1, 0, 0, 1, -1, 1, -1};
    int dy[] = {0, 0, -1, 1, 1, -1, -1, 1};

    v.clear();
    for (int i = 0; i < 8; i++)
    {
        int x = punct.first + dx[i];
        int y = punct.second + dy[i];

        if (x >= 1 && x <= m && y >= 1 && y <= n && matrice[x][y] != 'X')
        {
            v.push_back(make_pair(x, y));
        }
    }
}

void BFS(pair<int, int> start, vector<vector<bool>> &viz, vector<vector<int>> &d)
{
    queue<pair<int, int>> q;
    q.push(start);
    viz[start.first][start.second] = true;
    while (!q.empty())
    {
        pair<int, int> punct_curent = q.front();
        q.pop();
        vector<pair<int, int>> v;
        get_vecini(v, punct_curent);
        for (auto &vecin : v)
        {
            if (viz[vecin.first][vecin.second] == false)
            {
                q.push(vecin);
                d[vecin.first][vecin.second] = d[punct_curent.first][punct_curent.second] + 1;
                viz[vecin.first][vecin.second] = true;
            }
        }
    }
}

int main()
{
    Read();

    BFS(romeo, viz_r, d_r);
    BFS(julieta, viz_j, d_j);

    vector<vector<int>> puncte_intalnire;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (d_j[i][j] == d_r[i][j] && d_j[i][j] != 0)
                puncte_intalnire.push_back({i, j, d_j[i][j]});

    sort(puncte_intalnire.begin(), puncte_intalnire.end(), [](const vector<int> &a, const vector<int> &b)
         {
             if (a[2] != b[2])
                 return a[2] < b[2]; // Sortare descrescătoare după a[2]

             if (a[0] != b[0])
                 return a[0] < b[0]; // Sortare crescătoare după a[0] în caz de egalitate
                                     //
             return a[1] < b[1];     // Sortare crescătoare după a[0] în caz de egalitate
         });

    g << puncte_intalnire[0][2] + 1 << ' ' << puncte_intalnire[0][0] << ' ' << puncte_intalnire[0][1];

    return 0;
}