Cod sursa(job #1430212)

Utilizator danydin99Matei Daniel danydin99 Data 7 mai 2015 23:37:29
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.54 kb
#include <stdio.h>
using namespace std;

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


int ql[10609],qs[10609];
int mat_r[103][103], mat_j[103][103];
int timp[103][103];

int lee( int mat[103][103], int n, int m, int k1, int k2 )
{
    int i, j, s, d;

    ql[1] = k1;
    qs[1] = k2;
    s = 1; d = 1;

    while( s <= d ){

        if( qs[s]-1 != 0 && mat[ql[s]][qs[s]] + 1 < mat[ql[s]][qs[s]-1] ){
            d++;
            mat[ql[s]][qs[s]-1] =  mat[ql[s]][qs[s]] + 1;
            ql[d] = ql[s];
            qs[d] = qs[s]-1;
        }
        if( qs[s] != m && mat[ql[s]][qs[s]] + 1 < mat[ql[s]][qs[s]+1] ){
            d++;
            mat[ql[s]][qs[s]+1] =  mat[ql[s]][qs[s]] + 1;
            ql[d] = ql[s];
            qs[d] = qs[s]+1;
        }
        if( ql[s]-1 != 0 && mat[ql[s]][qs[s]] + 1 < mat[ql[s]-1][qs[s]] ){
            d++;
            mat[ql[s]-1][qs[s]] =  mat[ql[s]][qs[s]] + 1;
            ql[d] = ql[s]-1;
            qs[d] = qs[s];
        }
        if( ql[s] != n && mat[ql[s]][qs[s]] + 1 < mat[ql[s]+1][qs[s]]  ){
            d++;
            mat[ql[s]+1][qs[s]] =  mat[ql[s]][qs[s]] + 1;
            ql[d] = ql[s]+1;
            qs[d] = qs[s];
        }



        if( qs[s]-1 != 0  && ql[s]+1 != n + 1&& mat[ql[s]][qs[s]] + 1 < mat[ql[s]+1][qs[s]-1] ){
            d++;
            mat[ql[s]+1][qs[s]-1] =  mat[ql[s]][qs[s]] + 1;
            ql[d] = ql[s]+1;
            qs[d] = qs[s]-1;
        }
        if( qs[s] != m && ql[s] != 1 && mat[ql[s]][qs[s]] + 1 < mat[ql[s]-1][qs[s]+1] ){
            d++;
            mat[ql[s]-1][qs[s]+1] =  mat[ql[s]][qs[s]] + 1;
            ql[d] = ql[s]-1;
            qs[d] = qs[s]+1;
        }
        if( ql[s]-1 != 0 && qs[s] != 1 && mat[ql[s]][qs[s]] + 1 < mat[ql[s]-1][qs[s]-1] ){
            d++;
            mat[ql[s]-1][qs[s]-1] =  mat[ql[s]][qs[s]] + 1;
            ql[d] = ql[s]-1;
            qs[d] = qs[s]-1;
        }
        if( ql[s] != n && qs[s] != m && mat[ql[s]][qs[s]] + 1 < mat[ql[s]+1][qs[s]+1] ){
            d++;
            mat[ql[s]+1][qs[s]+1] =  mat[ql[s]][qs[s]] + 1;
            ql[d] = ql[s]+1;
            qs[d] = qs[s]+1;
        }
         s++;
    }
    return 0;
}


int main()
{
    int n, m, i, j, k1, k2, s1, s2, x1, x2, t;
    char x[121];
    t = 99999999; x1 = 0; x2 = 0;

    fscanf(in,"%d%d%*c",&n,&m);
    for( i = 1; i <= n; ++i ){
    fgets(x,m+20,in);
    for( j = 1; j <= m; ++j )
            if( x[j-1] == 'X' ){
                    mat_r[i][j] = -1;
                    mat_j[i][j] = -1;
            }
            else if( x[j-1] == 'J' ){
                    k1 = i;
                    k2 = j;
                    mat_r[i][j] = 999999999;
                    mat_j[i][j] = 0;
            }
            else if( x[j-1] == 'R' ){
                    s1 = i;
                    s2 = j;
                    mat_j[i][j] = 999999999;
                    mat_r[i][j] = 0;
            }
            else {
                    mat_r[i][j] = 999999999;
                    mat_j[i][j] = 999999999;
            }
    }
    lee( mat_r, n, m, s1, s2 );
    lee( mat_j, n, m, k1, k2 );

    for( i = 1; i <= n; ++i ){
        for( j = 1; j <= m; ++j )
        if( mat_j[i][j] != 999999999 && mat_r[i][j] != 999999999 && mat_j[i][j] != -1 && mat_r[i][j] != -1)
            if ( mat_r[i][j] ==  mat_j[i][j] && mat_r [i][j]< t ){
                    t = mat_r[i][j];
                    x1 = i; x2 = j;
            }
    }
    t++;
    fprintf(out,"%d %d %d",t,x1,x2);


}