Cod sursa(job #549317)

Utilizator rares192Preda Rares Mihai rares192 Data 8 martie 2011 13:48:06
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<fstream>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;

ofstream fout("rj.out");
#define mp make_pair

void read();
void solve();

int R[105][105], J[105][105];
char a[105][105];
int n, m;

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

queue< pair<pair<int , int> , int> > Q, Q1;
int iR, jR;
int iJ, jJ;

int main()
{
	read();
	solve();
	return 0;
}

void read()
{
	ifstream fin("rj.in");
	fin >> n >> m;
	
	char c[150];
	fin.get();
	for(int i = 0; i < n; ++i)
	{
			fin.getline( c, 150);
			strcpy(a[i], c);
	}
	
	for(int i = 0; i < n; ++i)
			for(int j = 0; j < m; ++j)
			{
				if( a[i][j] == 'R' ) { iR = i; jR = j; };
				if( a[i][j] == 'J' ) { iJ = i; jJ = j; };
			}
			
	fin.close();
}

void solve()
{	
	//ROMEO
	
	Q.push( mp( mp(iR, jR), 0) );
	R[iR][jR] = -1;
	
	while( !Q.empty() )
	{
		int l = Q.front().first.first;
		int c = Q.front().first.second;
		int d = Q.front().second;
		
		for(int k = 0; k < 8; ++k)
		{
			int l1 = l + dx[k];
			int c1 = c + dy[k];
			if( a[l1][c1] == ' ' && !R[l1][c1] && l1 >= 0 && l1 < n && c1 >= 0 && c1 < m)
			{
				Q.push( mp( mp(l1, c1), d + 1) );
				R[l1][c1] = d + 1;
			}
		}
		Q.pop();
	}
	
	//JULIETA
	
	Q1.push( mp( mp(iJ, jJ), 0) );
	J[iJ][jJ] = -1;
	
	while( !Q1.empty() )
	{
		int l = Q1.front().first.first;
		int c = Q1.front().first.second;
		int d = Q1.front().second;
		
		for(int k = 0; k < 8; ++k)
		{
			int l1 = l + dx[k];
			int c1 = c + dy[k];
			if( a[l1][c1] == ' ' && !J[l1][c1] && l1 >= 0 && l1 < n && c1 >= 0 && c1 < m)
			{
				Q1.push( mp( mp(l1, c1), d + 1) );
				J[l1][c1] = d + 1;
			}
		}
		Q1.pop();
	}
	
	
	//AFISARE
	int is, js, minim = 10000000;
	for( int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j)
			if( R[i][j] == J[i][j] && R[i][j] < minim && R[i][j] != 0)
			{
				minim = R[i][j];
				is = i;
				js = j;
			}
			
	fout << minim + 1 << " " << is + 1 <<" "<< js + 1;
	
}