Cod sursa(job #3249860)

Utilizator murgurazvan991Murgu Razvan Tudor murgurazvan991 Data 18 octombrie 2024 15:54:55
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.18 kb
// link - https://www.infoarena.ro/problema/rj
// 

#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

ifstream fin ("rj.in");
ofstream fout ("rj.out");

int n, m, xr, xj, yr, yj;
vector<vector<int>> a, b;
bool vizitat[176][176];

int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

void AfiseazaMatrice();
void Bordare();
void Citire();
void Colorare();
void Gaseste();

int main()
{
    Citire();
    Bordare();
    Colorare();

    for (int i = 1; i <= n; ++i, cout << '\n')
        for (int j = 1; j <= m; ++j)
            if (a[i][j] >= 0)
                cout << ' ' << a[i][j] << ' ';
            else 
                cout << a[i][j] << ' ';
    
    cout << '\n';

    for (int i = 1; i <= n; ++i, cout << '\n')
        for (int j = 1; j <= m; ++j)
            if (b[i][j] >= 0)
                cout << ' ' << b[i][j] << ' ';
            else 
                cout << b[i][j] << ' ';

    Gaseste();

    
    return 0;
}

void AfiseazaMatrice()
{
    for (int i = 1; i <= n; ++i, cout << '\n')
        for (int j = 1; j <= m; ++j)
            if (a[i][j] == ' ')
                cout << 0;
            else
                cout << a[i][j];
}

void Bordare()
{
    for(int i = 0; i <= n + 1; ++i)
        a[i][0] = a[i][m + 1] = b[i][0] = b[i][m + 1] = -1;
    for(int j = 0; j <= m + 1; ++j)
        a[0][j] = a[n + 1][j] = b[0][j] = b[n + 1][j] = -1;
}

void Citire()
{
    fin >> n >> m;
    a.resize(n + 2, vector<int>(m + 2, 0));
    b.resize(n + 2, vector<int>(m + 2, 0));
    fin.get();

    char c;
    for (int i = 1; i <= n; ++i, fin.get())
        for (int j = 1; j <= m; ++j)
        {
            fin.get(c);
            if (c == 'R')
                xr = i, yr = j;
            if (c == 'J')
                xj = i, yj = j;
            if (c == 'X')
                a[i][j] = b[i][j] = -1;
        }
            
}

void Colorare()
{  
    int i, j, x, y;
    queue<pair<int, int>> q;

    // Romeo
    q.emplace(xr, yr);
    a[xr][yr] = 1;
    while (!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (int k = 0; k < 8; ++k)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (!a[x][y])
            {
                a[x][y] = a[i][j] + 1;
                q.emplace(x, y);
            }
        }
    }

    // Julieta
    q.emplace(xj, yj);
    b[xj][yj] = 1;
    while (!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (int k = 0; k < 8; ++k)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (!b[x][y])
            {
                b[x][y] = b[i][j] + 1;
                q.emplace(x, y);
            }
        }
    }
}

void Gaseste()
{
    int i, j, mini = 1001, x, y;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= m; ++j)
            if(a[i][j] > 0 && a[i][j] == b[i][j])
            {
                if(a[i][j] < mini)
                    mini = a[i][j], x = i, y = j;
            }
    fout << mini << ' ' << x << ' ' << y;
}