Cod sursa(job #1095025)

Utilizator serban_ioan97Ciofu Serban serban_ioan97 Data 30 ianuarie 2014 11:27:53
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
# include <iostream>
# include <fstream>
# define Inf 2000

using namespace std;

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

int n , m, st, dr, R[120][120], J[120][120], xr, yr, xj, yj, DistMin, xmin, ymin;
char M[120][120];

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

struct Element
{
    int x,y;
};
Element Q[10000],val;

inline void Read()
{

    f>>n>>m;
    f.get();
    int i;
    for (i=1; i<=n; i++)
        f.getline((M[i]+1), 120);
    f.close();
}

inline void Bordare()
{
    int n1, i, m1;
    n1 = n + 1;
    m1 = m + 1;
    for (i = 0; i <= n1; i++)
        M[i][0] = M[i][m1] = 'X';
    for (i = 0; i <= m1; i++)
        M[0][i] = M[n1][i] = 'X';

}

inline void Initializare()
{
    int i,j;
    for( i = 1 ; i <= n ; ++i )
        for( j = 1 ; j <= m ; ++j )
            R[i][j] = J[i][j] = Inf;
}

inline void Search()
{
    int i,j;
    for( i = 1 ; i <= n ; ++i)
        for( j = 1  ; j <= m ; ++j )
        {
            if( M[i][j] == 'R' )
            {
                xr = i;
                yr = j;
            }
            if( M[i][j] == 'J' )
            {
                xj = i;
                yj = j;
            }
        }
}

inline void Lee( int x, int y, int v[][120] )
{
    int coordx,coordy,i,j,k,d;
    st = 0;
    dr = 0;
    Q[dr].x = x;
    Q[dr].y = y;

    while( st <= dr )
    {
        coordx = Q[st].x;
        coordy = Q[st].y;
        d = v[coordx][coordy];
        st++;

        for( k = 0 ; k < 8 ; ++k )
        {
            i = coordx + dx[k];
            j = coordy + dy[k];
            if( M[i][j] != 'X' && (v[i][j] > d + 1) )
            {
                dr++;
                Q[dr].x = i;
                Q[dr].y = j;
                v[i][j] = d + 1;
            }
        }
    }
}



inline void Solve()
{
    int i,j;
    DistMin = Inf;

    Read();
    Bordare();
    Initializare();
    Search();

    R[xr][yr] = 1;
    J[xj][yj] = 1;

    Lee(xr,yr,R);
    Lee(xj,yj,J);

    for ( i = 1 ; i <= n; ++i )
    {
        for( j = 1 ; j <= m ; ++j )
        {
            if (R[i][j] == J[i][j] && DistMin > R[i][j] )
            {
                DistMin = R[i][j];
                xmin = i;
                ymin = j;
            }
        }
    }


    g<<DistMin<<" "<<xmin<<" "<<ymin<<"\n";
    g.close();

}
int main()
{
    Solve();
    return 0;
}