Cod sursa(job #1885731)

Utilizator PetrescuRobertPetrescu Robert Mihai PetrescuRobert Data 20 februarie 2017 11:43:55
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <bits/stdc++.h>
using namespace std ;

const int MAX = 102 ;

bool copac [MAX] [MAX] ;
int distR [MAX] [MAX] ;
int distJ [MAX] [MAX] ;

bool inside(int, int, int, int);
void Lee(int, int, int[][102], int, int);

bool inside ( int i , int j , int n , int m )
{
    if ( i < 1 )
        return false ;
    if ( i > n )
        return false ;
    if ( j < 1 )
        return false ;
    if ( j > m )
        return false ;
    return true ;
}

queue < pair < int , int > > Q ;

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

ifstream fin ("rj.in") ;
ofstream fout ("rj.out") ;

char sir [MAX] ;

void Lee ( int xs , int ys , int dist [][MAX] , int n, int m ) {
    Q.push (make_pair(xs,ys)) ;
    dist [xs] [ys] = 1 ;
    while (!Q.empty())
    {
        pair < int , int > cur = Q.front() ;
        Q.pop () ;
        for ( int i = 0 ; i <= 7 ; ++ i ) {
            int x = cur.first + dx [i] ;
            int y = cur.second + dy[i] ;
            if ( inside ( x, y, n , m) == false ) {
                continue ;
            }
            if ( copac [x] [y] == true ) {
                continue ;
            }
            if ( dist [x][y] == 0 or dist [x][y] > dist [cur.first] [cur.second] + 1) {
                dist [x][y] = dist [cur.first] [cur.second] + 1 ;
                Q.push (make_pair(x,y)) ;
            }
        }
    }
}

int main()
{
    int n , m ;
    fin>> n >> m ;
    fin.get() ;
    int xR, yR ;
    int xJ, yJ ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        fin.getline (sir, MAX) ;
        for ( int j = 0 ; j < m ; ++ j ) {
            if ( sir [j] == 'R' ) {
                xR = i ;
                yR = j + 1 ;
            }
            else if ( sir [j] == 'J' ) {
                xJ = i ;
                yJ = j + 1 ;
            }
            else if ( sir [j] == 'X') {
                copac [i][j + 1] = true ;
            }
        }
    }
    Lee ( xR, yR, distR, n, m ) ;
    Lee ( xJ, yJ, distJ, n, m ) ;
    int tmin = 1 << 29 ;
    int xsol , ysol ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( int j = 1 ; j <= m ; ++ j ) {
            if ( distR [i][j] == distJ [i][j] and distR [i][j] >= 1 ) {
                if ( tmin > distR [i][j] ) {
                    tmin = distR [i][j] ;
                    xsol = i ;
                    ysol = j ;
                }
            }
        }
    }
    fout << tmin << ' ' << xsol << ' ' << ysol;
    return 0 ;
}