Cod sursa(job #185878)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 26 aprilie 2008 12:29:37
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <stdio.h>
#define Nmax 201
int a[Nmax][Nmax];
int n,m;
int rx,ry,jx,jy;
const int lin[]={-1,1,0,1, 0,-1,-1, 1};
const int col[]={-1,1,1,0,-1, 0, 1,-1};

const int lin1[]={ 1, 0,1,1,0,-1,-1,-1};
const int col1[]={-1,-1,0,1,1, 0, 1,-1};

const int lin2[]={1,0,1, 1,-1,-1,-1, 0};
const int col2[]={1,1,0,-1, 1,-1, 0,-1};

const int lin3[]={-1,0,-1,-1, 1, 1,1,1};
const int col3[]={ 1,1, 0,-1, 1,-1,0,1};

const int lin4[]={-1,-1, 0, 1,-1,1,1,0};
const int col4[]={-1, 0,-1,-1, 1,1,0,1};
struct pnct{int a,b;};
pnct v[Nmax*4];
void read()
{
	char ch;
	freopen("rj.in", "r",stdin);
	freopen("rj.out", "w",stdout);
	scanf("%d%d\n",&n,&m);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			scanf("%c", &ch);
			a[i][j]=Nmax;
			if(ch=='X')
				a[i][j]=-1;
			if(ch=='R')
			{
				rx=i;
				ry=j;
			}
			if(ch=='J')
			{
				jx=i;
				jy=j;
			}
		}
		scanf("%c", &ch);
	}
}
void lee(int x,int y)
{
	for(int t=0;t<8;t++)
		if((a[x+lin[t]][y+col[t]]>a[x][y]+1))
		{
			a[x+lin[t]][y+col[t]]=a[x][y]+1;
			v[++v[0].a].a=x+lin[t];
			v[v[0].a].b=y+col[t];
		}
}
void solve()
{
	a[rx][ry]=0;
	v[++v[0].a].a=rx;
	v[v[0].a].b=ry;
	for(int i=1;i<=v[0].a;i++)
	{
		lee(v[i].a,v[i].b);
		/*for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=m;++j)
				if(a[i][j]!=-1 && a[i][j]!=Nmax)
					printf("%d ",a[i][j]);
				else
					if(a[i][j]==-1)
					printf("xx ");
					else
						printf("oo ");
			printf("\n");
		}
		printf("\n");*/
	}	
	int lin_m[10],col_m[10];
	if(jx<=rx && jy>=ry)
		for(int i=0;i<8;++i)
		{	
			lin_m[i]=lin1[i];
			col_m[i]=col1[i];
		}
	if(jx>rx && jy<ry)
		for(int i=0;i<8;++i)
		{	
			lin_m[i]=lin2[i];
			col_m[i]=col2[i];
		}	
	if(jx<=rx && jy>=ry)
		for(int i=0;i<8;++i)
		{	
			lin_m[i]=lin3[i];
			col_m[i]=col3[i];
		}
	if(jx>rx && jy<ry)
		for(int i=0;i<8;++i)
		{	
			lin_m[i]=lin4[i];
			col_m[i]=col4[i];
		}		
	int x=jx;
	int y=jy;
	v[0].a=0;
	/*for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
			printf("%d ",a[i][j]);
		printf("\n");
	}*/
	printf("%d %d\n",jx,jy);
	while(1)
	{
		for(int t=0;t<8;t++)
		if((a[x+lin_m[t]][y+col_m[t]]+1==a[x][y]))
		{
			x=x+lin_m[t];
			y=y+col_m[t];
			v[++v[0].a].a=x;
			v[v[0].a].b=y;
			break;
		}
		//printf("%d %d\n",x,y);
		if(x==rx && y==ry)
		break;
	}
	printf("%d %d %d",(v[0].a+3)/2,v[ (v[0].a+1)/2 ].a,v[ (v[0].a+1)/2 ].b);
}
int main()
{
	read();
	solve();
	return 0;
}