Cod sursa(job #2201605)

Utilizator PogonetPogonet Artiom Pogonet Data 5 mai 2018 11:39:14
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include<fstream>
#include<queue>
#include<cstring>
using namespace std;

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

#define NMAX  101
queue < pair <int , int > > coada;
int xr , yr , xj , yj , r[NMAX][NMAX] , jul[NMAX][NMAX] , n , m;
char com[NMAX][NMAX] , c;

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

void citire ()
{
    f >> n >> m;
    for (int i = 1; i <= m; ++i)
        com[0][i] = com[n+1][i] = 'X';
    for (int i = 1; i <= n; ++i)
        com[i][0] = com[i][m+1] = 'X';
    f.get(c);
    for (int i = 1; i<= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            f.get(c); com[i][j] = c;
            if (com[i][j] == 'R') {xr = i; yr = j; com[i][j] = ' ';}
            if (com[i][j] == 'J') {xj = i; yj = j; com[i][j] = ' '; }
        }
        f.get(c);
    }
}
bool verif( int i , int j)
{
    if (i < 1 || j < 1 || i > n || j > m)
        return false;
    if (com[i][j] != ' ')
        return false;
    return true;
}
void alglee ( int x0 , int y0 , int d[][NMAX])
{
    int x0_urmator , y0_urmator , i , j;
    d[x0][y0] = 1;
    coada.push(make_pair(x0 , y0));
    for (int t =1; t<=n; t++)
        for (int k=1; k<=m; k++)
            d[t][k]= 0;
    while (!coada.empty())
    {
        i = coada.front().first;
        j = coada.front().second;
        coada.pop();
        for (int directie = 0; directie < 8; ++directie)
        {
            x0_urmator = i + dx[directie];
            y0_urmator = j + dy[directie];
            if (verif (x0_urmator , y0_urmator) && d[x0_urmator][y0_urmator] == 0)
            {
                d[x0_urmator][y0_urmator] = 1 + d[i][j];
                coada.push(make_pair(x0_urmator , y0_urmator));
            }
        }
    }
}
int main ()
{
    citire ();
    int tmin = NMAX*NMAX; int xmin = -1; int ymin = -1;
    alglee (xr , yr , r);
    alglee(xj , yj , jul);
    for (int i = 1; i <= n; i++)
        for (int k = 1; k <= m; k++)
        if ( r[i][k] == jul[i][k] )
            if (r[i][k] < tmin && r[i][k] != 0)
                {tmin = r[i][k]; xmin = i; ymin = k;}
    g << tmin+ 1 << ' ' << xmin << ' ' << ymin << '\n';
    g.close ();
    return 0;
}