Cod sursa(job #1732993)

Utilizator silkMarin Dragos silk Data 23 iulie 2016 13:52:05
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <cstdio>
#include <cstring>
#define NMax 105
#define INF 1<<30

struct rj{ int x,y,z; };
rj COADA[NMax*NMax];

char deja[NMax][NMax];
char a[NMax][NMax];
int R[NMax][NMax];
int J[NMax][NMax];

int dirx[8]={-1,0,1,0,-1,-1,1,1};
int diry[8]={0,1,0,-1,1,-1,1,-1};

int main(){
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

    int i,j,N,M,solx,soly,tmin=INF,x,y,z,inc,sf;
    char go;

    scanf("%d %d",&N,&M);
    scanf("%c",&go);

    for( i = 1; i <= N; ++i )
    fgets( a[i] + 1, NMax - 1, stdin );

    for( i = 0; i <= N + 1; ++i ) a[i][0] = a[i][M+1] = 'X';
    for( j = 0; j <= M + 1; ++j ) a[0][j] = a[N+1][j] = 'X';

    for( i = 1; i <= N; ++i )
        for( j = 1; j <= M; ++j )
        if( a[i][j] == 'R' ) { x = i; y = j; break; }


    inc = sf = 0;
    COADA[inc].x = x;
    COADA[inc].y = y;
    COADA[inc].z = 1;
    R[x][y] = 1;
    deja[x][y] = 1;
    while( inc <= sf )
    {
        x = COADA[inc].x;
        y = COADA[inc].y;
        z = COADA[inc++].z;
        for( int k = 0; k < 8; ++k )
        if( a[ x + dirx[k] ][ y + diry[k] ] != 'X' && !deja[ x + dirx[k] ][ y + diry[k] ] )
        {
            COADA[++sf].x = x + dirx[k];
            COADA[sf].y = y + diry[k];
            COADA[sf].z = z + 1;

            R[ x + dirx[k] ][ y + diry[k] ] = z + 1;
            deja[ x + dirx[k] ][ y + diry[k] ] = 1;
        }
    }

    for( i = 1; i <= N; ++i )
        for( j = 1; j <= M; ++j ) deja[i][j] = 0;

    for( i = 1; i <= N; ++i )
        for( j = 1; j <= M; ++j )
        if( a[i][j] == 'J' ) { x = i; y = j; break; }

    inc = sf = 0;
    COADA[inc].x = x;
    COADA[inc].y = y;
    COADA[inc].z = 1;
    J[x][y] = 1;
    deja[x][y] = 1;
    while( inc <= sf )
    {
        x = COADA[inc].x;
        y = COADA[inc].y;
        z = COADA[inc++].z;
        for( int k = 0; k < 8; ++k )
        if( a[ x + dirx[k] ][ y + diry[k] ] != 'X' && !deja[ x + dirx[k] ][ y + diry[k] ] )
        {
            COADA[++sf].x = x + dirx[k];
            COADA[sf].y = y + diry[k];
            COADA[sf].z = z + 1;

            J[ x + dirx[k] ][ y + diry[k] ] = z + 1;
            deja[ x + dirx[k] ][ y + diry[k] ] = 1;
        }
    }

    for( i = 1; i <= N; ++i )
        for( j = 1; j <= M; ++j )
        if( R[i][j] && R[i][j] == J[i][j] && R[i][j] < tmin )
        { x = i; y = j; tmin = R[i][j]; }

    printf("%d %d %d\n",tmin,x,y);




return 0;
}