Cod sursa(job #921824)

Utilizator TheNechizFMI Razvan Birisan TheNechiz Data 21 martie 2013 16:33:52
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
// Rj
# include <fstream>
# include <cstring>
# include <limits>
using namespace std;

struct
{
    short x,y;
}c[10609];

char oras[103][103];
short R[103][103],Ri,Rj;
short J[103][103],Ji,Jj;

short n,m;
/*
    Nord = lin-1,col
    Nord-Est = lin-1,col+1
    Nord-Vest = lin-1,col-1

    Sud = lin+1,col
    Sud-Est = lin+1,col+1
    Sud-Vestt = lin+1,col-1

    Est = lin,col+1

    Vest = lin,col-1
*/

short dl[] = {-1,-1,-1,1,1,1,0,0};
short dc[] = {0,1,-1,0,1,-1,1,-1};

short tmin = numeric_limits<short>::max();
short x,y;

void Citeste()
{
    ifstream in("rj.in");
    short i,j;
    char* Rl,*Jl;
    in >> n >> m;
    in.getline(oras[0],103);
    for( i = 1 ; i <= n ; ++i )
    {
        in.getline(oras[i]+1,m+1);
        Rl = strchr(oras[i]+1,'R');
        Jl = strchr(oras[i]+1,'J');
        if( Rl )
        {
            Ri = i;
            Rj = Rl-oras[i];
        }
        if( Jl )
        {
            Ji = i;
            Jj = Jl -oras[i];
        }
    }
    in.close();
}

void Init( short mat[103][103] )
{
    short i,j;
    for( i = 1 ; i <= n ; ++i )
        for( j = 1 ; j <= m ; ++j )
            mat[i][j] = n*m;
}

bool In_oras( short lin ,short col , short x , short y )
{
    return ( lin+x >= 1 && lin+x <= n ) && ( col+y >= 1 && col+y <= m );
}

void Traseu( short drum[103][103] , short lin , short col )
{
    short i,j,ind = 0;
    c[0].x = lin;
    c[0].y = col;
    drum[lin][col] = 0;
    for( i = 0 ; i <= ind ; ++i )
    {
        lin = c[i].x;
        col = c[i].y;
        for( j = 0 ; j < 8 ; ++j )
            if( oras[lin+dl[j]][col+dc[j]] != 'X' && In_oras(lin,col,dl[j],dc[j]) && drum[lin+dl[j]][col+dc[j]] > drum[lin][col]+1 )
            {
                ++ind;
                c[ind].x = lin+dl[j];
                c[ind].y = col+dc[j];
                drum[lin+dl[j]][col+dc[j]] = drum[lin][col]+1;
            }
    }
}

void Rezolv()
{
    short i,j;
    for( i = 1 ; i <= n ; ++i )
        for( j = 1 ; j <= m ; ++j )
            if( R[i][j] == J[i][j] && R[i][j] < tmin )
            {
                tmin = R[i][j];
                x = i;
                y = j;
            }
    ++tmin;
}

void Tipar()
{
    ofstream out("rj.out");
    out << tmin << ' ' << x << ' ' << y;
    out.close();
}

int main()
{
    Citeste();

    // R
    Init(R);
    Traseu(R,Ri,Rj);
    // J
    Init(J);
    Traseu(J,Ji,Jj);

    Rezolv();

    Tipar();

    return 0;
}