Cod sursa(job #124141)

Utilizator mariussMarius Telespan mariuss Data 18 ianuarie 2008 12:56:12
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<stdio.h>
int n,m,i,k,v[100][100],r[1010][4],j[1010][4],e,aux,jdr,rdr,jst,rst;
char c,s[110];
int x[8]={ 0, 1,1,1,0,-1,-1,-1};
int y[8]={-1,-1,0,1,1, 1, 0,-1};
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	
	scanf("%d %d\n",&n,&m);
	
	for(i=1;i<=n;i++)
	{
		fgets(s,m+5,stdin);
		for(k=1;k<=m;k++)
		{
			c=s[k-1];
			if(c=='X')
				v[i][k]=1;
			else
			{
				if(c=='R')
				{
					r[1][1]=i;
					r[1][2]=k;
				}
				else
					if(c=='J')
					{
						j[1][1]=i;	
						j[1][2]=k;
						
					}
			}
		}
	}

	
	for(i=0;i<=n+1;i++)
		v[i][0]=v[i][m+1]=1;
	
	for(i=0;i<=m+1;i++)
		v[0][i]=v[n+1][i]=1;
		
	rst=0;
	jst=0;
	rdr=1;
	jdr=1;
	r[1][3]=1;
	j[1][3]=1;
	v[r[1][1]][r[1][2]]=2;
	v[j[1][1]][j[1][2]]=3;
	for(i=2;i<=1000;i++)
		r[i][3]=j[i][3]=99999;
		
	while(!aux)
	{
		rst++;
		if(rst<=rdr)
		{
		for(e=0;e<8;e++)
			if(v[ r[rst][1] + y[e] ][ r[rst][2] + x[e]]!=1&& v[ r[rst][1] + y[e] ][ r[rst][2] + x[e]]!=2)
			{
				rdr++;
				r[rdr][1]=r[rst][1]+y[e];
				r[rdr][2]=r[rst][2]+x[e];
				if(r[rdr][3]>r[rst][3]+1)
					r[rdr][3]=r[rst][3]+1;	
				if(v[ r[rdr][1] ][ r[rdr][2] ]==3)
					v[ r[rdr][1] ][ r[rdr][2]]=1;
				else
					v[ r[rdr][1] ][ r[rdr][2]]=2;
			}
		}	
//		for(i=1;i<=rdr;i++)
//			printf("%d %d | ",r[i][1],r[i][2]);
//		printf("\n");

		jst++;
		if(jst<=jdr)
		{
		for(e=0;e<8;e++)
			if(v[ j[jst][1] + y[e] ][ j[jst][2] + x[e]]!=1&& v[ j[jst][1] + y[e] ][ j[jst][2] + x[e]]!=3)
			{
				jdr++;
				j[jdr][1]=j[jst][1]+y[e];
				j[jdr][2]=j[jst][2]+x[e];
				if(j[jdr][3]>j[jst][3]+1)
					j[jdr][3]=j[jst][3]+1;	
				if(v[ j[jdr][1] ][ j[jdr][2]]==2)
					v[ j[jdr][1] ][ j[jdr][2]]=1;
				else
					v[ j[jdr][1] ][ j[jdr][2]]=3;
			}
		}	
//		for(i=1;i<=jdr;i++)
//			printf("%d %d | ",j[i][1],j[i][2]);
			
	
		for(i=1;i<=rdr;i++)
		{
			for(k=1;k<=jdr;k++)
				if(r[i][1]==j[k][1]&&r[i][2]==j[k][2]&&r[i][3]==j[k][3])
				{
					aux=1;
					break;
				}
			if(aux)
				break;
		}
			
	}
	
	printf("%d %d %d",r[i][3],r[i][1],r[i][2]);
	
	return 0;
	
}