Cod sursa(job #136301)

Utilizator devilkindSavin Tiberiu devilkind Data 15 februarie 2008 13:43:40
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <stdio.h>
#include <string.h>


#define NMAX 128

short int a[NMAX][NMAX];
short int R[NMAX][NMAX],J[NMAX][NMAX];
char viz[NMAX][NMAX];
short int n,m,i,j,k,sxr,syr,sxj,syj,dr,x,y;
short int solx,soly,sol;
char c;
short int cd[NMAX*NMAX][2];


int v[8][2];

int main()
{

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

scanf("%d %d\n",&n,&m);

for (i=1;i<=n;i++)
	{
	for (j=1;j<=m;j++)
		{
		c=fgetc(stdin);
		if (c=='X') a[i][j]=1;
		if (c=='R') {sxr=i;syr=j;}
		if (c=='J') {sxj=i;syj=j;}
		}
	scanf("\n");
	}

for (i=0;i<=n;i++)
	{
	a[i][0]=1;
	a[i][m+1]=1;
	}

for (i=0;i<=m;i++)
	{
	a[0][i]=1;
	a[n+1][i]=1;
	}

v[0][0]=-1;v[0][1]=-1;
v[1][0]=-1;v[1][1]=0;
v[2][0]=-1;v[2][1]=1;
v[3][0]=0;v[3][1]=-1;
v[4][0]=0;v[4][1]=1;
v[5][0]=1;v[5][1]=-1;
v[6][0]=1;v[6][1]=0;
v[7][0]=1;v[7][1]=1;

for (i=1;i<=n;i++)
	for (j=1;j<=m;j++)
		{
		R[i][j]=12000;
		J[i][j]=12000;
		}

cd[1][0]=sxr;cd[1][1]=syr;
R[sxr][syr]=1;
dr=1;

memset(viz,0,sizeof(viz));
viz[sxr][syr]=1;

for (i=1;i<=dr;i++)
	{
	x=cd[i][0];y=cd[i][1];

	for (j=0;j<8;j++)
		if ( (a[x+v[j][0]][y+v[j][1]]==0)&&(!viz[x+v[j][0]][y+v[j][1]]) )
					     {
					     viz[x+v[j][0]][y+v[j][1]]=1;
					     cd[++dr][0]=x+v[j][0];
					     cd[dr][1]=y+v[j][1];
					     R[x+v[j][0]][y+v[j][1]]=R[x][y]+1;
					     }
	}



cd[1][0]=sxj;cd[1][1]=syj;
J[sxj][syj]=1;
dr=1;

memset(viz,0,sizeof(viz));
viz[sxj][syj]=1;

for (i=1;i<=dr;i++)
	{
	x=cd[i][0];y=cd[i][1];

	for (j=0;j<8;j++)
		if ( (a[x+v[j][0]][y+v[j][1]]==0)&&(!viz[x+v[j][0]][y+v[j][1]]) )
					     {
					     viz[x+v[j][0]][y+v[j][1]]=1;
					     cd[++dr][0]=x+v[j][0];
					     cd[dr][1]=y+v[j][1];
					     J[x+v[j][0]][y+v[j][1]]=J[x][y]+1;
					     }
	}

/*for (i=1;i<=n;i++,printf("\n") )
	for (j=1;j<=m;j++)
		printf("%d ",R[i][j]);
printf("\n");
for (i=1;i<=n;i++,printf("\n") )
	for (j=1;j<=m;j++)
		printf("%d ",J[i][j]);*/


sol=12000;

for (i=1;i<=n;i++)
	for (j=1;j<=m;j++)
		{
		if (R[i][j]>J[i][j]) k=R[i][j];
			else k=J[i][j];

		if (k<sol) {sol=k;solx=i;soly=j;}

		}
printf("%d %d %d",sol,solx,soly);
return 0;
}