Cod sursa(job #1164696)

Utilizator EpictetStamatin Cristian Epictet Data 2 aprilie 2014 11:33:58
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
const int dl[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
const int dc[] = { -1, 0, 1, 1, 0, 1, -1, -1 };
typedef struct { int x,y; } cop;
short n,m,rx,ry,jx,jy,A[109][109];
queue < cop > R,J;
char c;

inline void Read_Data()
{
	f >> n >> m;
	f.get(c);
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			f.get(c);
			if(c == 'X') A[i][j] = 1;
			else if(c == 'R') rx = i, ry = j, A[rx][ry] = 1;
			else if(c == 'J') jx = i, jy = j, A[jx][jy] = 1;
		}
		f.get(c);
	}
	for(int i=0; i<=n+1; i++) A[i][0] = A[i][m+1] = 1;
	for(int j=0; j<=m+1; j++) A[0][j] = A[n+1][j] = 1;
}

inline void Solve()
{
	cop aux;
	aux.x = rx;
	aux.y = ry;
	R.push(aux);
	
	aux.x = jx;
	aux.y = jy;
	J.push(aux);
	
	int ok = 0;
	while(!ok)
	{
		int rl = R.front().x;
		int rc = R.front().y;
		int jl = J.front().x;
		int jc = J.front().y;
		R.pop();
		J.pop();
		
		if(rl == jl && rc == jc) ok = 1, g << A[rl][jc]-1 << " " << rl << " " << jc << '\n';
		else
		{
			for(int k=0; k<=7; k++)
			{
				int rll = rl + dl[k];
				int rcc = rc + dc[k];
				int jll = jl + dl[k];
				int jcc = jc + dc[k];
				
				if(A[rll][rcc] != 1)
				{
					A[rll][rcc] = A[rl][rc] + 1;
					aux.x = rll;
					aux.y = rcc;
					R.push(aux);
				}
				if(A[jll][jcc] != 1)
				{
					A[jll][jcc] = A[jl][jc] + 1;
					aux.x = jll;
					aux.y = jcc;
					J.push(aux);
				}
			}
		}
	}
}

int main()
{
	Read_Data();
	Solve();
	
	g.close();
	return 0;
}