Cod sursa(job #2101260)

Utilizator priboiraduPriboi Radu Bogdan priboiradu Data 7 ianuarie 2018 00:54:47
Problema Rj Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <stdio.h>
#include <stdlib.h>
#define N 100

int leeR[N + 2][N + 2], leeJ[N + 2][N + 2];
int dl[8] = { -1, -1, 0, 1, 1,  1,  0, -1 };
int dc[8] = {  0,  1, 1, 1, 0, -1, -1, -1 };
int prim, ultim;

struct gogu {
    int l, c;
} coada[4 * N];

void bordare( int x, int y ) {
    int i, j;
    for ( i = 0; i <= x + 1; i++ ) {
        leeR[i][0] = -1;
        leeR[i][y + 1] = -1;
        leeJ[i][0] = -1;
        leeJ[i][y + 1] = -1;
    }
    for ( j = 0; j <= y + 1; j++ ) {
        leeR[0][j] = -1;
        leeR[x + 1][j] = -1;
        leeJ[0][j] = -1;
        leeJ[x + 1][j] = -1;
    }
}

void enqueue( int lin, int col ) {
    coada[ultim].l = lin;
    coada[ultim].c = col;
    ultim = ( ultim + 1 ) % ( 4 * N );
}

void dequeue( int *lin, int *col ) {
    (*lin) = coada[prim].l;
    (*col) = coada[prim].c;
    prim = ( prim + 1 ) % ( 4 * N );
}

int emptyqueue( ) {
    return ( prim == ultim );
}

int main() {
    FILE *fin, *fout;
    int n, m, i, j, lR, cR, lJ, cJ, lin, col, dist, k, min, x, y;
    char c;
    fin = fopen( "rj.in", "r" );
    fout = fopen( "rj.out", "w" );
    fscanf( fin, "%d%d", &n, &m );
    fgetc( fin );
    for ( i = 1; i <= n; i++ ) {
        for ( j = 1; j <= m; j++ ) {
            c = fgetc( fin );
            if ( c == 'R' ) {
                lR = i;
                cR = j;
            } else if ( c == 'J' ) {
                lJ = i;
                cJ = j;
            } else if ( c == 'X' ) {
                leeR[i][j] = -1;
                leeJ[i][j] = -1;
            }
        }
        fgetc( fin );
    }
    bordare( n, m );
    prim = 0;
    ultim = 1;
    leeR[lR][cR] = 1;
    coada[prim].l = lR;
    coada[prim].c = cR;
    while ( !emptyqueue() ) {
        dequeue( &lin, &col );
        dist = leeR[lin][col] + 1;
        for ( k = 0; k < 8; k++ ) {
            if ( leeR[lin + dl[k]][col + dc[k]] == 0 ) {
                enqueue( lin + dl[k], col + dc[k] );
                leeR[lin + dl[k]][col + dc[k]] = dist;
            }
        }
    }
    prim = 0;
    ultim = 1;
    leeJ[lJ][cJ] = 1;
    coada[prim].l = lJ;
    coada[prim].c = cJ;
    while ( !emptyqueue() ) {
        dequeue( &lin, &col );
        dist = leeJ[lin][col] + 1;
        for ( k = 0; k < 8; k++ ) {
            if ( leeJ[lin + dl[k]][col + dc[k]] == 0 ) {
                enqueue( lin + dl[k], col + dc[k] );
                leeJ[lin + dl[k]][col + dc[k]] = dist;
            }
        }
    }
    min = 10000;
    for ( j = 1; j <= m; j++ ) {
        for ( i = 1; i <= n; i++ ) {
            if ( leeR[i][j] == leeJ[i][j] && leeR[i][j] > 0 && leeR[i][j] < min ) {
                min = leeR[i][j];
                x = i;
                y = j;
            }
        }
    }
    fprintf( fout, "%d %d %d", min, x, y );
    fclose( fin );
    fclose( fout );
    return 0;
}