Cod sursa(job #2668277)

Utilizator ADRIAN.CATRINOIUAdrian Catrinoiu ADRIAN.CATRINOIU Data 4 noiembrie 2020 18:38:10
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.55 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int romeo[102][102], julieta[102][102];
queue<pair<int, int>> coadabfs; //o coada pentru celulele speciale si nodurile in care am calculat distanta
int n, m, rx, ry, jx, jy;

void bfs(int pers[][102], int x, int y)
{
    int px, py, pozitie, currentx, currenty;
    coadabfs.push({x, y});
    while (!coadabfs.empty())
    {
        currentx = coadabfs.front().first;
        currenty = coadabfs.front().second;
        coadabfs.pop();

        for (pozitie = 0; pozitie < 8; pozitie++)
        {
            //stanga
            if (pozitie == 0)
            {
                px = currentx - 1;
                py = currenty;
            }
            //dreapta
            if (pozitie == 1)
            {
                px = currentx + 1;
                py = currenty;
            }
            //sus
            if (pozitie == 2)
            {
                px = currentx;
                py = currenty + 1;
            }
            //jos
            if (pozitie == 3)
            {
                px = currentx;
                py = currenty - 1;
            }
            //stanga sus
            if (pozitie == 4)
            {
                px = currentx - 1;
                py = currenty + 1;
            }
            //dreapta sus
            if (pozitie == 5)
            {
                px = currentx + 1;
                py = currenty + 1;
            }
            //stanga jos
            if (pozitie == 6)
            {
                px = currentx - 1;
                py = currenty - 1;
            }
            //dreapta jos
            if (pozitie == 7)
            {
                px = currentx + 1;
                py = currenty - 1;
            }
            //daca nu iesim din matrice
            if (currentx >= 1 && currentx <= n && currenty >= 1 && currenty <= m)
                //daca nu am mai ajuns pana acum pe acest drum atunci distanta pana aici este nodul curent+1
                if (pers[px][py] == 0)
                {
                    pers[px][py] = pers[currentx][currenty] + 1;
                    coadabfs.push({px, py});
                }
        }
    }
}
int main()
{
    int i, j;
    char c[101];
    fin >> n >> m;
    fin.get();
    for (i = 1; i <= n; i++)
    {
        fin.getline(c, 101);
        for (j = 0; j < m; j++)
        {

            //marcam pozitia lui Romeo cu 1
            if (c[j] == 'R')
            {
                romeo[i][j + 1] = 1;
                rx = i;
                ry = j + 1;
            }
            //marcam pozitia Julietei cu 1
            else if (c[j] == 'J')
            {
                julieta[i][j + 1] = 1;
                jx = i;
                jy = j + 1;
            }
            //marcam pozitiile prin care nu se poate trece cu -1
            else if (c[j] == 'X')
            {
                romeo[i][j + 1] = -1;
                julieta[i][j + 1] = -1;
            }
        }
    }
    // for (i = 1; i <= n; i++)
    // {
    //     for (j = 1; j <= m; j++)
    //     {
    //         fout << romeo[i][j] << " ";
    //     }
    //     fout << endl;
    // }
    // for (i = 1; i <= n; i++)
    // {
    //     for (j = 1; j <= m; j++)
    //     {
    //         fout << julieta[i][j] << " ";
    //     }
    //     fout << endl;
    // }

    //vom parcurge cu un bfs de la ambii pentru a vedea distanta minima comuna
    bfs(romeo, rx, ry);
    bfs(julieta, jx, jy);

    // for (i = 1; i <= n; i++)
    // {
    //     for (j = 1; j <= m; j++)
    //     {
    //         fout << romeo[i][j] << " ";
    //     }
    //     fout << endl;
    // }
    // for (i = 1; i <= n; i++)
    // {
    //     for (j = 1; j <= m; j++)
    //     {
    //         fout << julieta[i][j] << " ";
    //     }
    //     fout << endl;
    // }
    //luam o variabila drum_min pentru a verifica care este drumul cel mai optim gasit si
    //vom memora unde se intalnesc cei doi in rjx,rjy
    int drum_min = INT_MAX, rjx = 0, rjy = 0;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            //daca distantele sunt egale si drumul este valid(>0) si cel mai scurt
            if (romeo[i][j] == julieta[i][j] && romeo[i][j] < drum_min && julieta[i][j] > 0)
            {
                drum_min = romeo[i][j];
                rjx = i;
                rjy = j;
            }
        }
    fout << drum_min << " " << rjx << " " << rjy;
    return 0;
}