Cod sursa(job #3240742)

Utilizator raulthestormIlie Raul Ionut raulthestorm Data 20 august 2024 18:31:54
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

int n, m, xj, yj, xr, yr;

vector<vector<int>> a, b;
queue<pair<int, int>> q;

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

void citire()
{
    int i, j;
    char c;
    f >> n >> m;
    a.resize(n + 2, vector<int>(m + 2, 0));
    b.resize(n + 2, vector<int>(m + 2, 0));
    for(i = 1; i <= n; ++i)
    {
        f.get();
        for(j = 1; j <= m; ++j)
        {
            f.get(c);
            if(c == 'R')
                xr = i, yr = j;
            else
                if(c == 'J')
                    xj = i, yj = j;
                else
                    if(c == 'X')
                        a[i][j] = b[i][j] = -1;
        }
    }
}

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 Lee()
{
    int i, j, k, x, y;
    ///Romeo
    q.emplace(xr, yr);
    a[xr][yr] = 1;
    while(!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for(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(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 = 205, 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;
            }
    g << mini << ' ' << x << ' ' << y;
}

int main()
{
    citire();
    bordare();
    Lee();
    gaseste();
    f.close();
    g.close();
    return 0;
}