Cod sursa(job #2841357)

Utilizator Matei_MunteanuMunteanu Matei Ioan Matei_Munteanu Data 29 ianuarie 2022 16:40:46
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n;
int m;
int ma_r[105][105];   // matricea pentru drumul lui Romeo
int ma_j[105][105];   // matricea pentru drumul Julietei
int xrstart, yrstart; // poz de inceput a lui Romeo
int xjstart, yjstart; // poz de inceput a Julietei
const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
queue<pair<int, int>> R; // coada pt algoritm lee Romeo
queue<pair<int, int>> J; // coada pt algoritm lee Julieta
bool prima_sol = true;
bool is_inside(int x, int y)
{
    return (1 <= x && x <= n && 1 <= y && y <= m);
}
void lee_romeo(int istart, int jstart)
{
    ma_r[istart][jstart] = 1;
    R.push(make_pair(istart, jstart));
    while (!R.empty())
    {
        int icurent, jcurent;
        icurent = R.front().first;
        jcurent = R.front().second;
        R.pop();
        for (int d = 0; d < 8; d++)
        {
            int inou, jnou;
            inou = icurent + dx[d];
            jnou = jcurent + dy[d];
            if (is_inside(inou, jnou) && ma_r[inou][jnou] == 0)
            {
                ma_r[inou][jnou] = ma_r[icurent][jcurent] + 1;
                R.push(make_pair(inou, jnou));
            }
        }
    }
}
void lee_julieta(int istart, int jstart)
{
    ma_j[istart][jstart] = 1;
    J.push(make_pair(istart, jstart));
    while (!J.empty())
    {
        int icurent, jcurent;
        icurent = J.front().first;
        jcurent = J.front().second;
        J.pop();
        for (int d = 0; d < 8; d++)
        {
            int inou, jnou;
            inou = icurent + dx[d];
            jnou = jcurent + dy[d];
            if (is_inside(inou, jnou) && ma_j[inou][jnou] == 0)
            {
                ma_j[inou][jnou] = ma_j[icurent][jcurent] + 1;
                J.push(make_pair(inou, jnou));
            }
        }
    }
}
int main()
{
    fin >> n >> m;
    fin.get();
    for (int i = 1; i <= n; i++)
    {
        char a;
        for (int j = 1; j <= m; j++)
        {
            a = fin.get();
            if (a == 'R')
            {
                xrstart = i;
                yrstart = j;
            }
            else if (a == 'J')
            {
                xjstart = i;
                yjstart = j;
            }
            else if (a == 'X')
            {
                ma_j[i][j] = -1;
                ma_r[i][j] = -1;
            }
            else
            {
                ma_j[i][j] = 0;
                ma_r[i][j] = 0;
            }
        }
        fin.get();
    }
    lee_romeo(xrstart, yrstart);
    lee_julieta(xjstart, yjstart);
    int irez = 0;
    int jrez = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if(ma_j[i][j] > 0 && ma_r[i][j] >= 0 && ma_j[i][j] == ma_r[i][j])
            {
                if(prima_sol)
                {
                    irez = i;
                    jrez = j;
                    prima_sol = false;
                }
                else
                {
                    if(ma_j[i][j] < ma_j[irez][jrez])
                    {
                        irez = i;
                        jrez = j;
                    }
                }
            }
        }
    }
    fout << ma_j[irez][jrez] << ' ' << irez << ' ' << jrez;
    return 0;
}