Cod sursa(job #801099)

Utilizator mihaitsMihai Zavoian mihaits Data 23 octombrie 2012 14:51:03
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>
#include <climits>
using namespace std;
ifstream fin ( "rj.in" );
ofstream fout ( "rj.out" );

int m, n, r[101][101], J[101][101], lir, cir, lij, cij, qed = INT_MAX, qi, qj;
char t[101][101];

int main()
{
	fin >> n >> m;
	
	fin.get();
	for ( int i = 0; i < n; i ++ )
	{
		fin.getline( t[i], 101 );
	}
	for ( int i = 0; i < n; i ++ )
		for ( int j = 0; j < m; j ++ )
		{
			
			if ( t[i][j] == 'X' )
			{
				r[i+1][j+1] = -1;
				J[i+1][j+1] = -1;
			}
			if ( t[i][j] == 'R' )
			{
				r[i+1][j+1] = 1;
				J[i+1][j+1] = 0;
				lir = i + 1;
				cir = j + 1;
			}
			if ( t[i][j] == 'J' )
			{
				r[i+1][j+1] = 0;
				J[i+1][j+1] = 1;
				lij = i + 1;
				cij = j + 1;
			}
		}
	
	int di[] = { -1, 0, 1, 0, -1, 1, 1, -1};
	int dj[] = { 0, -1, 0, 1, -1, 1, -1, 1};
	int c[10000], l[10000], st, dr;
	st = dr = 0;
	c[dr] = cir;
	l[dr++] = lir;
	while ( st <= dr )
	{
		int i = l[st], j = c[st];
		for ( int k = 0; k < 4 ; k ++ )
		{
			int ii = i + di[k], jj = j + dj[k];
			if ( ii > 0 && ii <= n && jj > 0 && jj <= m && r[ii][jj] == 0 )
			{
				r[ii][jj] = r[i][j] + 1;
				l[dr] = ii;
				c[dr] = jj;
				dr ++;
			}
		}
		st ++;
	}
	
	st = dr = 0;
	c[dr] = cij;
	l[dr++] = lij;
	while ( st <= dr )
	{
		int i = l[st], j = c[st];
		for ( int k = 0; k < 4 ; k ++ )
		{
			int ii = i + di[k], jj = j + dj[k];
			if ( ii > 0 && ii <= n && jj > 0 && jj <= m && J[ii][jj] == 0 )
			{
				J[ii][jj] = J[i][j] + 1;
				l[dr] = ii;
				c[dr] = jj;
				dr ++;
			}
		}
		st ++;
	}
	
	for ( int i = 1; i <= n; i ++ )
	{
		for ( int j = 1; j <= m; j ++ )
		{
			if ( r[i][j] == J[i][j] && r[i][j] != -1 && r[i][i] < qed )
			{
				qed = r[i][j];
				qi = i;
				qj = j;
			}
		}
	}
	fout << qed;
	for ( int i = 1; i <= n; i ++ )
	{
		for ( int j = 1; j <= m; j ++ )
		{
			if ( r[i][j] == qed && r[i][j] == J[i][j] )
			{
				fout << ' ' << i << ' ' << j;
			}
		}
	}
	
	fin.close();
	fout.close();
}