Cod sursa(job #555666)

Utilizator ZethpixZethpix Zethpix Data 15 martie 2011 18:03:44
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <stdio.h>
#include <string.h>

int i,j,rx,ry,jx,jy,x,y,M,N,end,drum;
int A[101][101],B[101][101];
int dx[8]={-1,0,1,-1,1,-1,0,1};
int dy[8]={-1,-1,-1,0,0,1,1,1};
char ch;
char sir[110];

struct queue
{
	int x,y;
	queue *link;
}*C1,*C2,*aux;

inline void add(int x,int y)
{
	queue *p;

	p=new queue;
	p->x=x;
	p->y=y;
	p->link=C2;
	C2=p;
}

int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);

	scanf("%d %d\n",&M,&N);

	memset(A,0,sizeof(A));
	memset(B,0,sizeof(B));

	for(i=1;i<=M;i++)
	{
		fgets(sir,N+2,stdin);
		for(j=1;j<=N;j++)
		{
			ch=sir[j-1];

			if(ch=='X') A[i][j]=-1;
			else
			if(ch==' ') A[i][j]=0;
			else
			if(ch=='R')
			{
				A[i][j]=0;
				rx=i;
				ry=j;
			}
			else
			if(ch=='J')
			{
				A[i][j]=0;
				jx=i;
				jy=j;
			}
			B[i][j]=A[i][j];
		}
	}

	end=0;
	A[jx][jy]=-1;
	A[rx][ry]=1;

	C1=new queue;
	C1->x=rx;
	C1->y=ry;
	C1->link=NULL;
	C2=new queue;
	C2=NULL;

	while(!end)
	{
		while(C1!=NULL)
		{
			x=C1->x;
			y=C1->y;
			aux=C1;
			C1=C1->link;
			delete aux;

			for(i=0;i<8;i++)
				if((0<x+dx[i])&&(x+dx[i]<=M)&&(0<y+dy[i])&&(y+dy[i]<=N))
					if(A[x+dx[i]][y+dy[i]]==0)
					{
						A[x+dx[i]][y+dy[i]]=A[x][y]+1;
						add(x+dx[i],y+dy[i]);
					}
		}

		C1=C2;
		C2=NULL;
		if(C1==NULL)
		{
			end=0;
			break;
		}
	}

	end=0;
	B[jx][jy]=1;
	B[rx][ry]=-1;

	C1=new queue;
	C1->x=jx;
	C1->y=jy;
	C1->link=NULL;
	C2=new queue;
	C2=NULL;

	while(!end)
	{
		while(C1!=NULL)
		{
			x=C1->x;
			y=C1->y;
			aux=C1;
			C1=C1->link;
			delete aux;

			for(i=0;i<8;i++)
				if((0<x+dx[i])&&(x+dx[i]<=M)&&(0<y+dy[i])&&(y+dy[i]<=N))
					if(B[x+dx[i]][y+dy[i]]==0)
					{
						B[x+dx[i]][y+dy[i]]=B[x][y]+1;
						add(x+dx[i],y+dy[i]);
					}
		}

		C1=C2;
		C2=NULL;
		if(C1==NULL)
		{
			end=0;
			break;
		}
	}

	drum=N*M+1;
	x=0;
	y=0;

	for(i=1;i<=M;i++)
		for(j=1;j<=N;j++)
			if(A[i][j]>0&&B[i][j]>0&&A[i][j]==B[i][j])
				if(drum>A[i][j])
				{
					drum=A[i][j];
					x=i;
					y=j;
				}

	printf("%d %d %d\n",drum,x,y);

	return 0;
}