Cod sursa(job #77534)

Utilizator DastasIonescu Vlad Dastas Data 14 august 2007 15:50:15
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <cstdio>

const int maxn = 101;
const int inf = 200000;

FILE *in = fopen("rj.in","r"), *out = fopen("rj.out","w");

int n, m;
int ro[maxn][maxn];
int ju[maxn][maxn];

int srx, sry;
int sjx, sjy;

void read()
{
    fscanf(in, "%d %d\n", &n, &m);

    char c[maxn];
    for ( int i = 1; i <= n; ++i )
    {
        fgets(c, maxn, in);
        for ( int j = 0; j < m; ++j )
        {
            if ( c[j] == 'X' )
                ro[i][j+1] = ju[i][j+1] = -1;
            else if ( c[j] == 'R' )
                srx = i, sry = j+1, ro[srx][sry] = 1;
            else if ( c[j] == 'J' )
                sjx = i, sjy = j+1, ju[sjx][sjy] = 1;
            else if ( c[j] = ' ' )
                ro[i][j+1] = ju[i][j+1] = inf;

        }
    }
}

struct coada
{
    short x, y;
};

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

void BFr()
{
    coada C[maxn*maxn];

    int p = 0, u = 0;
    C[p].x = srx, C[p].y = sry;

    while ( p <= u )
    {
        for ( int i = 0; i < 8; ++i )
        {
            int X = C[p].x + dx[i];
            int Y = C[p].y + dy[i];

            if ( ro[X][Y] > ro[C[p].x][C[p].y] + 1 )
            {
                ro[X][Y] = ro[C[p].x][C[p].y] + 1;
                ++u;
                C[u].x = X;
                C[u].y = Y;
            }
        }
        ++p;
    }
}

void BFj()
{
    coada C[maxn*maxn];

    int p = 0, u = 0;
    C[p].x = sjx, C[p].y = sjy;

    while ( p <= u )
    {
        for ( int i = 0; i < 8; ++i )
        {
            int X = C[p].x + dx[i];
            int Y = C[p].y + dy[i];

            if ( ju[X][Y] > ju[C[p].x][C[p].y] + 1 )
            {
                ju[X][Y] = ju[C[p].x][C[p].y] + 1;
                ++u;
                C[u].x = X;
                C[u].y = Y;
            }
        }
        ++p;
    }
}

int main()
{
    read();

    BFr();
    BFj();

    int min = inf;
    int x = 0, y = 0;

//    for ( int i = 1; i <= n; ++i )
//    {
//        for ( int j = 1; j <= m; ++j )
//            printf("%d ", ro[i][j]);
//        printf("\n");
//    }
//    printf("\n");
//    for ( int i = 1; i <= n; ++i )
//    {
//        for ( int j = 1; j <= m; ++j )
//            printf("%d ", ju[i][j]);
//        printf("\n");
//    }
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
            if ( ro[i][j] == ju[i][j] && ro[i][j] < min && ro[i][j] != -1 )
                min = ro[i][j], x = i, y = j;

    fprintf(out, "%d %d %d\n", min, x, y);

	return 0;
}