Cod sursa(job #542206)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 25 februarie 2011 22:38:36
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<stdio.h>

typedef struct {int xx;int yy;} queue;

int a[105][105],rom[105][105],jul[105][105],i,j,n,m,xr,yr,xj,yj,min,xf,yf;
int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};
char c;

inline void drum(int d[105][105],int xi,int yi)
{
	queue q[20000];
	int ii,st=0,dr=0,x,y;
	
	q[st].xx=xi; q[st].yy=yi;
	while(st<=dr)
	{
		x=q[st].xx; y=q[st].yy;
		
		for(ii=0;ii<8;ii++)
			if( !a[x+dx[ii]][y+dy[ii]] && !d[x+dx[ii]][y+dy[ii]] 
				&& x+dx[ii]>0 && y+dy[ii]>0 && x+dx[ii]<n+1 && y+dy[ii]<m+1 )
			{
				++dr;
				q[dr].xx=x+dx[ii]; q[dr].yy=y+dy[ii];
				d[q[dr].xx][q[dr].yy]=d[x][y]+1;
			}
		
		++st;
	}
	
	return;
}

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++)
		{
			scanf("%c",&c);
			if(c=='X') a[i][j]=1;
			else if(c!=' ')
			{
				if(c=='R')
				{
					xr=i;
					yr=j;
				}
				else if(c=='J')
				{
					xj=i;
					yj=j;
				}
			}
		}
		scanf("%c",&c);
	}
	
	drum(rom,xr,yr);
	drum(jul,xj,yj);
	
	min=2000000000;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(rom[i][j]&&rom[i][j]==jul[i][j]&&rom[i][j]<min)
			{
				min=rom[i][j];
				xf=i; yf=j;
			}
	
	printf("%d %d %d\n",min+1,xf,yf);
	
	return 0;
}