Cod sursa(job #661104)

Utilizator Coman95coman cosmin Coman95 Data 13 ianuarie 2012 19:57:26
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include<fstream>
#include<queue>
using namespace std;

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

const int di[] = { 1, 0, -1, 0, -1, 1, 1, -1 },
		  dj[] = { 0, -1, 0, 1, 1, 1, -1, -1 };	

struct poz{
	int x;
	int y;
};
  
#define INF 0x3f3f3f3f
int a[101][101];
int b[101][101];
char str[200]; 
poz v[200];
char y;
int n, m, ir ,ij ,jr, jj;
int iv, jv;

bool Inside(int i, int j);


int main()
{
	fin >> n >> m;
	fin.getline(str, 200);
	for ( int i = 1; i <= n; i++ )
	{
		fin.getline(str, 200);
		for( int j = 1; j <= m; j++ )
		{
			if ( str[j-1] == 'R' )
			{
				a[i][j] = 1;
				ir = i;
				jr = j;
			}
			else if ( str[j-1] == 'J' )
			{
				b[i][j] = 1;
				ij = i;
				jj = j;
			}
			else if( str[j-1] == 'X' )
			{
				a[i][j] = -1;
				b[i][j] = -1;
			}
		}
	}
	int i, j;
	/*for (  i = 1; i <= n; i++ )
	{
			for(  j = 1; j <= m; j++ )
				fout << a[i][j]<< ' ';
		fout << '\n';
	}
	fout << '\n';
	for (  i = 1; i <= n; i++ )
	{
			for(  j = 1; j <= m; j++ )
				fout << b[i][j]<< ' ';
		fout << '\n';
	}
	fout << '\n';
	*/
	
	
	queue<pair<int,int> > Q;
	Q.push(make_pair(ir, jr));
	while ( !Q.empty() )
	{
		i = Q.front().first;
		j = Q.front().second;
		//fout << i << ' ' << j << '\n';
		Q.pop();
		for ( int d = 0; d < 8; ++d )
		{
			iv = i + di[d];
			jv = j + dj[d];
			if ( Inside(iv, jv) && a[iv][jv] == 0 )
			{
				Q.push(make_pair(iv, jv));
				a[iv][jv] = a[i][j] + 1;	
			}
		}
	}
	//fout << '\n';
	Q.push(make_pair(ij, jj));
	while ( !Q.empty() )
	{
		i = Q.front().first;
		j = Q.front().second;
		//fout << i << ' ' << j << '\n';
		Q.pop(); 
		for ( int d = 0; d < 8; ++d )
		{
			iv = i + di[d];
			jv = j + dj[d];
			if ( Inside(iv, jv) && b[iv][jv] == 0 )
			{
				Q.push(make_pair(iv, jv));
				b[iv][jv] = b[i][j] + 1;	
			}
		}
	}
	
	
	
	/*for (  i = 1; i <= n; i++ )
	{
			for(  j = 1; j <= m; j++ )
				fout << a[i][j]<< ' ';
		fout << '\n';
	}
	fout << '\n';
	for (  i = 1; i <= n; i++ )
	{
			for(  j = 1; j <= m; j++ )
				fout << b[i][j]<< ' ';
		fout << '\n';
	}
	fout << '\n';*/
	
	int k = 0;
	for ( int i = 1; i <= n; i++ )
		for ( int j = 1; j <= m; j++ )
		{
			if( a[i][j] == b[i][j] && a[i][j] > 0 )
			{
				v[++k].x = i;
				v[k].y = j;
			}
		}
	poz aux;
	int min = INF;
	//for ( int i = 1; i <= k; i++ )
		//fout << v[i].x << ' ' << v[i].y << '\n';
	for ( int i = 1; i <= k; i++ )
		if ( a[v[1].x][v[1].y] < min )
			min = a[v[1].x][v[1].y];
		
	for ( int i = 1; i <= k; i++ )
		for( int j = i; j <= k; j++ )
			if ( v[i].x > v[j].x && a[v[1].x][v[1].y] == min )
			{
				aux = v[i];
				v[i] = v[j];
				v[j] = aux;
			}
	fout << a[v[1].x][v[1].y] << ' ' << v[1].x << ' ' << v[1].y << '\n';
	fin.close();
	fout.close();
	return 0;
}

bool Inside(int i, int j)
{
	return i > 0 && i <= n && j > 0 && j <= m;
}