Cod sursa(job #680522)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 15 februarie 2012 18:43:24
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<fstream>
#include<queue>
#define NMAX 103

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

short a[2][NMAX][NMAX], n, m, Ri, Rj, Ji, Jj;
short di[8]={-1, -1, -1, 0, 0, 1, 1, 1};
short dj[8]={-1, 0, 1, -1, 1, -1, 0, 1};

struct coada
{
	char i, j;
};
queue<coada> q;

void Citeste()
{
	int i, j;
	char x[NMAX];
	f>>n>>m; f.get();
	for (i=1; i<=n; ++i)
	{
		f.getline(x, NMAX);
		for (j=0; j<m; ++j)
			if (x[j]=='X') a[0][i][j+1]=-1, a[1][i][j+1]=-1;
			else if (x[j]=='R') Ri=i, Rj=j+1;
				else if (x[j]=='J') Ji=i, Jj=j+1;
	}
	for (i=0; i<=n+1; ++i)
		a[0][i][0]=a[0][i][m+1]=a[1][i][0]=a[1][i][m+1]=-1;
	for (j=0; j<=m+1; ++j)
		a[0][0][j]=a[0][n+1][j]=a[1][0][j]=a[1][n+1][j]=-1;
}

void Lee(int x, int i, int j)
{
	int k;
	coada r, w;
	r.i=i; r.j=j; q.push(r); a[x][i][j]=1;
	while (!q.empty())
	{
		r=q.front(); q.pop();
		for (k=0; k<8; ++k)
		{
			i=r.i+di[k]; j=r.j+dj[k];
			if (a[x][i][j]==0)
			{
				a[x][i][j]=a[x][(int)r.i][(int)r.j]+1;
				w.i=i; w.j=j; q.push(w);
			}
		}
	}
}

void Solve()
{
	int i, j, I, J, pasi=NMAX*NMAX;
	for (i=1; i<=n; ++i)
		for (j=1; j<=m; ++j)
			if (a[0][i][j]>0 && a[0][i][j]==a[1][i][j] && pasi>a[0][i][j]) pasi=a[0][i][j], I=i, J=j;
	g<<pasi<<" "<<I<<" "<<J<<"\n";
}

int main()
{
	Citeste();
	Lee(0, Ri, Rj);
	Lee(1, Ji, Jj);
	Solve();
	f.close();
	g.close();
	return 0;
}