Cod sursa(job #2495232)

Utilizator NopeCarp Rafael Nope Data 18 noiembrie 2019 23:07:19
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <bits/stdc++.h>
#define oo 2000000
using namespace std;

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

char a[102][102];
int n , m;
int xr , yr , xj , yj;
int Rom[102][102];
int Jul[102][102];
int dx[8]={-1 , -1 ,  0 , 1 , 1 ,  1 , 0 ,  -1};
int dy[8]={ 0 ,   1 , 1 , 1 , 0 , -1 , -1 , -1};
queue <pair <int , int > > q;

void Citire()
{
    int i , j;
    fin >> n >> m;
    fin.get();
    for (i = 1 ; i <= n ; i++)
        fin.getline((a[i] + 1) , 102);
    for (i = 1 ; i <= n ; i++)
        for (j = 1 ; j <= m ; j++)
        {
            if (a[i][j] == 'R')
            { xr = i ; yr = j;}
            if (a[i][j] == 'J')
            { xj = i ; yj = j;}
            Rom[i][j] = oo;
            Jul[i][j] = oo;
        }
}

inline bool Inside(int x , int y)
{
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}

void LeeRom(int c , int d)
{
    int i , j , x , y , k;
    Rom[c][d] = 1;
    q.push({c , d});
    while(!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (k = 0 ; k < 9 ; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (Inside(x , y) && a[x][y] != 'X' &&
                Rom[x][y] > Rom[i][j] + 1)
            {
                Rom[x][y] = Rom[i][j] + 1;
                q.push({x , y});
            }
        }
    }
}

void LeeJul(int c , int d)
{
    int x , y , i , j , k;
    Jul[c][d] = 1;
    q.push({c , d});
    while(!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (k = 0 ; k < 9 ; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (Inside(x , y) &&
                a[x][y] != 'X' &&
                Jul[x][y] > Jul[i][j] + 1)
            {
                Jul[x][y] = Jul[i][j] + 1;
                q.push({x , y});
            }
        }
    }
}

int main()
{
    Citire();
    LeeRom(xr , yr);
    LeeJul(xj , yj);
    int mn , i , j;
    int xrasp , yrasp;
    mn = oo;
    for (i = 1 ; i <= n ; i++)
        for (j = 1 ; j <= m ; j++)
            if (a[i][j] != 'X' &&
                Rom[i][j] == Jul[i][j]
                && Rom[i][j] != oo)
                {
                    if (Rom[i][j] < mn)
                    {
                        mn = Rom[i][j];
                        xrasp = i;
                        yrasp = j;
                    }
                }
    fout << mn << " " << xrasp << " " << yrasp <<"\n";
    return 0;
}