Cod sursa(job #1857761)

Utilizator SpiristulTeribilStefan Vilcu SpiristulTeribil Data 26 ianuarie 2017 17:04:09
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <queue>

using namespace std ;

const int MAX = 102 ;

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

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 cin ("rj.in") ;
ofstream cout ("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 ;
	cin >> n >> m ; 
	cin.get() ;
	int xR, yR ;
	int xJ, yJ ; 
	for ( int i = 1 ; i <= n ; ++ i ) {
		cin.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 ; 
			}
		}
	}
	//cout << xR << ' ' << yR << '\n' ; 
	//cout << xJ << ' ' << yJ << '\n' ; 
	//return 0 ; 
	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 ;
				}
			}
		}
	}
	cout << tmin << ' ' << xsol << ' ' << ysol << '\n' ;
	return 0 ; 
}