Cod sursa(job #885229)

Utilizator tudorv96Tudor Varan tudorv96 Data 21 februarie 2013 19:12:43
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <queue>
using namespace std;

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

int R[105][105], J[105][105], m, n, t = 2000000;
struct tail {
	int x, y;
} sr, sj, meet;
queue <tail> coada;

tail init (int x, int y)
{
	tail a;
	a.x = x, a.y = y;
	return a;
}

void Lee (int a[][105], tail s, tail f)
{
	coada.push(s);
	a[s.x][s.y] = 1;
	while (coada.size())
	{
		int i = coada.front().x;
		int j = coada.front().y;
		for (int k = 0; k < 8; k++)
		{
			int ii = i + dx[k];
			int jj = j + dy[k];
			if (ii >= 0 && jj >= 0 && ii < m && jj < n && !a[ii][jj])
			{
				a[ii][jj] = a[i][j] + 1;
				coada.push(init (ii, jj));
			}
		}
		coada.pop();
	}
}

int main ()
{
	char v[105];
	ifstream fin ("rj.in");
	fin >> m >> n;
	fin.get();
	for (int i = 0; i < m; ++i)
	{
		fin.getline (v, 105);
		for (int j = 0; j < n; ++j)
		{
			if (v[j] == 'X')
				R[i][j] = J[i][j] = -1;
			if (v[j] == 'R')
				sr.x = i, sr.y = j;
			if (v[j] == 'J')
				sj.x = i, sj.y = j;
		}
	}
	fin.close ();
	ofstream fout ("rj.out");
	Lee (R, sr, sj);
	Lee (J, sj, sr);
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < n; ++j)
			if (R[i][j] == J[i][j] && R[i][j] > 0 && R[i][j] < t) 
			{
				meet.x = i;
				meet.y = j;
				t = R[i][j];
			}
	fout << t << " " << meet.x + 1 << " " << meet.y + 1;
	fout.close ();
	return 0;
}