Cod sursa(job #1218146)

Utilizator ConstantinPetroviciPetrovici Constantin ConstantinPetrovici Data 9 august 2014 17:51:04
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

#define mp make_pair
#define f first
#define s second

using namespace std;

int n , m , r[109][109] , ju[109][109] , xr , yr , xj , yj;
int dx[]={-1,0,1,1,1,0,-1,-1};
int dy[]={-1,-1,-1,0,1,1,1,0};

char sir [ 109 ] ;
typedef pair <int,int> P;


void lee1( int x , int y )
{
    r[x][y]=1;
    queue <P> q;
    q.push(mp(x,y));
    while (!q.empty())
    {
        int temp_x=q.front().f;
        int temp_y=q.front().s;
        for ( int i = 0 ; i <= 7 ; ++i)
            if( r[temp_x+dx[i]][temp_y+dy[i]] == 0 )
            {
                r[temp_x+dx[i]][temp_y+dy[i]]=r[temp_x][temp_y]+1;
                q.push(mp(temp_x+dx[i],temp_y+dy[i]));
            }
        q.pop();
    }
}
void lee2( int x , int y )
{
    ju[x][y]=1;
    queue <P> q;
    q.push(mp(x,y));
    while (!q.empty())
    {
        int temp_x=q.front().f;
        int temp_y=q.front().s;
        for ( int i = 0 ; i <= 7 ; ++i)
            if( ju[temp_x+dx[i]][temp_y+dy[i]] == 0 )
            {
                ju[temp_x+dx[i]][temp_y+dy[i]]=ju[temp_x][temp_y]+1;
                q.push(mp(temp_x+dx[i],temp_y+dy[i]));
            }
        q.pop();
    }
}
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)
        {
            r[i][0]=r[i][m+1]=-1;
            ju[i][0]=ju[i][m+1]=-1;
        }
    for ( int i = 0 ; i <= m+1 ; ++i)
        {
            r[0][i]=r[n+1][i]=-1;
            ju[0][i]=ju[n+1][i]=-1;
        }
    for ( int i = 1 ; i <= n ;++i )
        {
            gets( sir + 1 );
            for( int j = 1 ; j <= m ; ++j )
            {
            if (sir [ j ] =='X'){
                        r[i][j]=-1;
                        ju[i][j]=-1;
                        }
            if (sir [ j ] =='R'){
                        xr=i;
                        yr=j;
                        }
            if (sir [ j ] =='J'){
                        xj=i;
                        yj=j;
                        }
            }
        }
    //for(int i= 1 ; i <= n ; ++i , printf("\n"))
    //    for(int j= 1 ; j <= m ; ++j,printf("%3d ",r[i][j]));
    //printf("\n\n\n\n");
    //for(int i= 1 ; i <= n ; ++i , printf("\n"))
    //    for(int j= 1 ; j <= m ; ++j,printf("%3d ",ju[i][j]));
    //printf("\n\n\n\n");
    lee1(xr,yr);
    lee2(xj,yj);
    int tmin=99999,lin,col;
    for(int i= 1 ; i <= n ; ++i )
        for(int j= 1 ; j <= m ; ++j )
            if((r[i][j]==ju[i][j]) and (r[i][j]<tmin ) and r [ i ] [ j ] >1 )
                {
                tmin=r[i][j];
                lin=i;
                col=j;
                }
    printf("%d %d %d" , tmin , lin , col);
    //for(int i= 1 ; i <= n ; ++i , printf("\n"))
   //    for(int j= 1 ; j <= m ; ++j)
    //    printf("%3d ",r[i][j]);
   // printf("\n\n\n\n");
    //for(int i= 1 ; i <= n ; ++i , printf("\n"))
    //    for(int j= 1 ; j <= m ; ++j)
    //        printf("%3d ",ju[i][j]);
    return 0;
}