Cod sursa(job #550861)

Utilizator halianStefanca Stefan halian Data 9 martie 2011 23:15:02
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <stdio.h>
const int ad[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

struct co
{
	short x,y;
} r,j,leer[5000],leej[5000],rez;

int mat[102][102],dist;
short n,m;

void cit()
{
	int i,t;
	char c;
	FILE *f=fopen("rj.in","r");
	fscanf(f,"%i%i%*c",&n,&m);
	for(i=1;i<=n;i++)
	{
		for(t=1;t<=m;t++)
		{
			fscanf(f,"%c",&c);
			switch(c)
			{
			case 'R':
				r.x=i;
				r.y=t;
				mat[i][t]=-1;
				break;
			case 'X':
				mat[i][t]=-1;
				break;
			case 'J':
				j.x=i;
				j.y=t;
				mat[i][t]=-1;
				break;
			}
		}
		fscanf(f,"%*c");
	}
}

void init()
{
	short lim,i;
	if(m>n)
		lim=m;
	else
		lim=n;
	lim++;
	for(i=0;i<=lim;i++)
		mat[i][0]=mat[0][i]=mat[n+1][i]=mat[i][m+1]=-1;
}

void rezolvare()
{
	int ir,ij,jr,jj,i,distr,distj,pr,pj;
	ir=ij=0;
	jr=jj=distr=distj=pr=pj=1;
	leej[0]=j;
	leer[0]=r;
	while(dist==0)
	{
		while(distj==distr)
		{	
			for(i=0;i<8;i++)
				if(mat[leej[ij].x+ad[i][0]][leej[ij].y+ad[i][1]]==0)
				{
					mat[leej[ij].x+ad[i][0]][leej[ij].y+ad[i][1]]=distj;
					leej[jj].x=leej[ij].x+ad[i][0];
					leej[jj].y=leej[ij].y+ad[i][1];
					jj++;
				}
			ij++;
			if(ij==pj)
			{
				pj=jj;
				distj++;
			}
		}
		while(distj>distr)
		{
			for(i=0;i<8;i++)
				if(mat[leer[ir].x+ad[i][0]][leer[ir].y+ad[i][1]]==distr)
					{
						dist=distr;
						if(leer[ir].x+ad[i][0]<rez.x)
						{
							rez.x=leer[ir].x+ad[i][0];
							rez.y=leer[ir].y+ad[i][1];
						}
						else
							if(leer[ir].x+ad[i][0]==rez.x && leer[ir].y+ad[i][1]<rez.y)
							{
								rez.x=leer[ir].x+ad[i][0];
								rez.y=leer[ir].y+ad[i][1];
							}
					}
				else
					if(mat[leer[ir].x+ad[i][0]][leer[ir].y+ad[i][1]]==0)
					{
						mat[leer[ir].x+ad[i][0]][leer[ir].y+ad[i][1]]=-1;
						leer[jr].x=leer[ir].x+ad[i][0];
						leer[jr].y=leer[ir].y+ad[i][1];
						jr++;
					}
			ir++;
			if(ir==pr)
			{
				pr=jr;
				distr++;
			}
		}
	}
}

int main()
{
	rez.x=101;
	rez.y=101;
	cit();
	init();
	rezolvare();
	fprintf(fopen("rj.out","w"),"%i %i %i",dist+1,rez.x,rez.y);
	return 0;
}