Cod sursa(job #77769)

Utilizator megabyteBarsan Paul megabyte Data 14 august 2007 20:04:38
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <cstdio>
#define INF "rj.in"
#define OUF "rj.out"
#define NMAX 128
#define QMAX 512
#define BIG 32000
using namespace std;
short n,m;
char inmap[NMAX][NMAX];

struct coord
{
	short x,y;
};

void fill(short c[][NMAX],int ln,int cl)
{
   short dx[8]={-1,-1,-1,0,1,1, 1, 0};
   short dy[8]={-1, 0, 1,1,1,0,-1,-1};
   short d1,d2,nx,ny,x,y,pred,i,j,ok;

   coord alfa[QMAX],beta[QMAX],*p,*q,*aux;
   p=alfa;q=beta;
   d1=1;d2=0;p[d1].x=ln;p[d1].y=cl;
   for(i=1;i<=n;++i)
	   for(j=1;j<=m;++j)if(inmap[i][j]=='X') c[i][j]=-1;
		              else  c[i][j]=BIG;
   c[ln][cl]=0;

   while(d1)
   {
	   for(i=1;i<=d1;++i)
	   {
		x=p[i].x;
		y=p[i].y;
		pred=c[x][y]+1;
		for(j=0;j<8;++j)
		{
			nx=x+dx[j];
			ny=y+dy[j];
			if(nx>0&&nx<=n&&ny>0&&ny<=m&&pred<c[nx][ny])
			{
				c[nx][ny]=pred;
				++d2;
				q[d2].x=nx;
				q[d2].y=ny;
			}
		}
	   }
	   d1=d2;d2=0;
	   aux=p;p=q;q=aux;
   }
}

int main()
{
	short rm[NMAX][NMAX],jl[NMAX][NMAX],i,j;
	coord ro,ju,rez;
	char buf[NMAX];
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	rez.x=ro.x=ju.x=0;
	rez.y=ro.y=ju.y=0;

	fscanf(in,"%hd%hd\n",&n,&m);
	for(i=1;i<=n;++i)
	{
		fgets(buf,NMAX,in);	
//		printf("%s\n",buf);
		for(j=1;j<=m;++j)
		{
		       	inmap[i][j]=buf[j-1];
			if(inmap[i][j]=='R')     {ro.x=i;ro.y=j;}
			else if(inmap[i][j]=='J'){ju.x=i;ju.y=j;}
	//		printf("%c",inmap[i][j]);
		}
	//	printf("\n");
	}
//	printf("%hd %hd\n",ju.x,ju.y);

	fill(rm,ro.x,ro.y);
	fill(jl,ju.x,ju.y);	
	
	/*for(i=1;i<=n;++i)
	{
		for(j=1;j<=m;++j) printf("%hd ",rm[i][j]);
		printf("\n");
	}
	printf("\n");
	for(i=1;i<=n;++i)
	{
		for(j=1;j<=m;++j) printf("%hd ",jl[i][j]);
		printf("\n");
	}
*/
	rm[0][0]=jl[0][0]=BIG;rez.x=0;rez.y=0;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			if(rm[i][j]==jl[i][j]&&rm[i][j]>0&&rm[i][j]<rm[rez.x][rez.y])
			{
				rez.x=i;
				rez.y=j;
			}

	fprintf(out,"%hd %hd %hd\n",rm[rez.x][rez.y]+1,rez.x,rez.y);
	fclose(in);fclose(out);
	return 0;
}