Cod sursa(job #681225)

Utilizator dragangabrielDragan Andrei Gabriel dragangabriel Data 16 februarie 2012 19:40:31
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include<cstdio>
#include<deque>
int xx,yy,n,i,j,k,r[105][105],jj[105][105],rez1,rez2,rez3,m,rx,ry,jy,jx;
char a[120][120];
using namespace std;
deque<int>x,y;
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d %d/n",&n,&m);
	for (i=0;i<=n;i++) 
	{
	fgets(a[i],110,stdin);
	for (j=0;j<=m;j++) if (a[i][j]=='R') rx=i,ry=j+1,r[i][j+1]=1;else
		if (a[i][j]=='J') jx=i,jy=j+1,jj[i][j+1]=1;else
			if (a[i][j]=='X') r[i][j+1]=-1,jj[i][j+1]=-1;
	scanf("/n");
	}
	for (i=0;i<=n;i++) r[i][0]=-1,r[i][m+1]=-1,jj[i][0]=-1,jj[i][m+1]=-1;
	for (i=0;i<=m;i++) r[0][i]=-1,r[n+1][i]=-1,jj[0][i]=-1,jj[n+1][i]=-1;
	x.push_back(rx);y.push_back(ry);
	while (!x.empty()) {
		xx=x.front();yy=y.front();
		if (r[xx-1][yy-1]==0) {
			r[xx-1][yy-1]=r[xx][yy]+1;
			x.push_back(xx-1);y.push_back(yy-1);}
		if (r[xx+1][yy+1]==0) {
			r[xx+1][yy+1]=r[xx][yy]+1;
			x.push_back(xx+1);y.push_back(yy+1);}
		if (r[xx+1][yy-1]==0) {
			r[xx+1][yy-1]=r[xx][yy]+1;
			x.push_back(xx+1);y.push_back(yy-1);}
		if (r[xx-1][yy+1]==0) {
			r[xx-1][yy+1]=r[xx][yy]+1;
			x.push_back(xx-1);y.push_back(yy+1);}
		if (r[xx][yy-1]==0) {
			r[xx][yy-1]=r[xx][yy]+1;
			x.push_back(xx);y.push_back(yy-1);}
		if (r[xx][yy+1]==0) {
			r[xx][yy+1]=r[xx][yy]+1;
			x.push_back(xx);y.push_back(yy+1);}
		if (r[xx-1][yy]==0) {
			r[xx-1][yy]=r[xx][yy]+1;
			x.push_back(xx-1);y.push_back(yy);}
		if (r[xx+1][yy]==0) {
			r[xx+1][yy]=r[xx][yy]+1;
			x.push_back(xx+1);y.push_back(yy);}
		x.pop_front();
		y.pop_front();		
	}
		x.push_back(jx);y.push_back(jy);
	while (!x.empty()) {
		xx=x.front();yy=y.front();
		if (jj[xx-1][yy-1]==0) {
			jj[xx-1][yy-1]=jj[xx][yy]+1;
			x.push_back(xx-1);y.push_back(yy-1);}
		if (jj[xx+1][yy+1]==0) {
			jj[xx+1][yy+1]=jj[xx][yy]+1;
			x.push_back(xx+1);y.push_back(yy+1);}
		if (jj[xx-1][yy+1]==0) {
			jj[xx-1][yy+1]=jj[xx][yy]+1;
			x.push_back(xx-1);y.push_back(yy+1);}
		if (jj[xx+1][yy-1]==0) {
			jj[xx+1][yy-1]=jj[xx][yy]+1;
			x.push_back(xx+1);y.push_back(yy-1);}
		if (jj[xx][yy-1]==0) {
			jj[xx][yy-1]=jj[xx][yy]+1;
			x.push_back(xx);y.push_back(yy-1);}
		if (jj[xx][yy+1]==0) {
			jj[xx][yy+1]=jj[xx][yy]+1;
			x.push_back(xx);y.push_back(yy+1);}
		if (jj[xx-1][yy]==0) {
			jj[xx-1][yy]=jj[xx][yy]+1;
			x.push_back(xx-1);y.push_back(yy);}
		if (jj[xx+1][yy]==0) {
			jj[xx+1][yy]=jj[xx][yy]+1;
			x.push_back(xx+1);y.push_back(yy);}
		x.pop_front();
		y.pop_front();		
	}
	rez3=9999999;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++) if ((rez3>r[i][j])&&(r[i][j]==jj[i][j])&&(r[i][j]>0))
			rez3=r[i][j],rez1=i,rez2=j;
	printf("%d %d %d",rez3,rez1,rez2);
	return 0;
}