Cod sursa(job #877848)

Utilizator matei_cChristescu Matei matei_c Data 13 februarie 2013 12:42:19
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 kb
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<vector>
using namespace std ;

#define maxn 101
#define maxcoada 10001
#define maxdir 8

char sir[maxn] ;

struct punct
{
    int x, y ;
};

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

int n, m ;
char harta[maxn][maxn] ;

int xr, yr ;
int xj, yj ;

int romeo[maxn][maxn] ;
int julieta[maxn][maxn] ;

void lee(int xs, int ys, int dist[maxn][maxn] )
{

    punct coada[maxcoada] ;

    for(int i = 0; i <= n + 1; ++i )
        for(int j = 0; j <= m + 1 ; ++j )
            dist[i][j] = -1 ;

    int len = 0 ;

    coada[len].x = xs ;
    coada[len].y = ys ;
    dist[xs][ys] = 1 ;

    for(int i = 0; i <= len; ++i )
    {
        int xn = coada[i].x ;
        int yn = coada[i].y ;

        for(int j = 0; j < maxdir; ++j )
        {
            int xact = xn + dx[j] ;
            int yact = yn + dy[j] ;

            if( harta[ xact ][ yact ] == ' ' && dist[ xact ][ yact ] == -1 )
            {
                dist[ xact ][ yact ] = dist[xn][yn] + 1 ;
                ++len ;
                coada[len].x = xact ;
                coada[len].y = yact ;
            }
        }
    }
}

int main()
{

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

    scanf("%d%d\n", &n, &m);

    for(int i = 0; i <= n + 1; ++i )
        harta[i][0] = harta[i][ m + 1 ] = 'X' ;

    for(int i = 0; i <= m + 1; ++i )
        harta[0][i] = harta[ n + 1 ][i] = 'X' ;

    for(int i = 1; i <= n; ++i )
    {

        fgets( sir, maxn+5, stdin ) ;

      //  cout<<strlen(sir)<<" "<<sir<<endl ;

        for(int j = 1; j <= m; ++j )
        {
            harta[i][j] = sir[j-1] ;

            if( harta[i][j] == 'R' )
            {
                xr = i ;
                yr = j ;
                harta[i][j] = ' ' ;
            }

            if( harta[i][j] == 'J' )
            {
                xj = i ;
                yj = j ;
                harta[i][j] = ' ' ;
            }


        }
        /*

        char ch ;

        for(int j = 1; j <= m; ++j )
        {
            scanf("%c", &ch);
            harta[i][j] = ch ;

            if( harta[i][j] == 'R' )
            {
                xr = i ;
                yr = j ;
                harta[i][j] = ' ' ;
            }

            if( harta[i][j] == 'J' )
            {
                xj = i ;
                yj = j ;
                harta[i][j] = ' ' ;
            }
        }

        scanf("%c", &ch);
*/
    }

    lee( xr, yr, romeo ) ;

    lee( xj, yj, julieta ) ;

    int tmin = maxcoada ;
    int xmin, ymin ;

    for(int i = 1; i <= n; ++i )
    {
        for(int j = 1; j <= m; ++j )
        {
            if( romeo[i][j] == julieta[i][j] )
            {
                if( romeo[i][j] < tmin && romeo[i][j] != -1 )
                {
                    tmin = romeo[i][j] ;
                    xmin = i ;
                    ymin = j ;
                }
            }
        }
    }

    printf("%d %d %d\n", tmin, xmin, ymin);

    return 0 ;

}