Cod sursa(job #1217935)

Utilizator ConstantinPetroviciPetrovici Constantin ConstantinPetrovici Data 8 august 2014 21:13:35
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 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 , 1 , 0 , 0 , -1 , -1 , 1 , 1 };
int dy[]={ 0 , 0 , 1 , -1 , -1 , 1 , 1 , -1 };

typedef pair <int,int> P;

queue <P> q;
void lee( int x , int y , int mat[109][109])
{
    mat[x][y]=1;
    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(!mat[temp_x+dx[i]][temp_y+dy[i]])
            {
                mat[temp_x+dx[i]][temp_y+dy[i]]=mat[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 )
        {
            char c;
            for( int j = 1 ; j <= m ; ++j )
            {
            scanf ("%c" , &c );
            if (c=='X'){
                        r[i][j]=-1;
                        ju[i][j]=-1;
                        }
            if (c=='R'){
                        xr=i;
                        yr=j;
                        }
            if (c=='J'){
                        xj=i;
                        yj=j;
                        }
            }
            scanf ( "\n" ) ;
        }
    //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");
    lee(xr,yr,r);
    lee(xj,yj,ju);
    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 and r [ i ] [ j ] )
                {
                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;
}