Cod sursa(job #131879)

Utilizator mariussMarius Telespan mariuss Data 4 februarie 2008 17:01:22
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<stdio.h>
#include<string.h>
#define nmax 110

char s[nmax],a[nmax][nmax];
int i,j,k,n,m,viz[nmax][nmax],xx[nmax*nmax],yy[nmax*nmax];
int R[nmax][nmax],J[nmax][nmax];
int dx[8]={-1,-1,0,1,1, 1, 0,-1};
int dy[8]={ 0, 1,1,1,0,-1,-1,-1};

void df(int x,int y, int dist[nmax][nmax])
{
	int p=0,q=1;
	int x1,y1;

	memset(viz,0,sizeof(viz));
	xx[1]=x;
	yy[1]=y;
	viz[x][y]=dist[x][y]=1;

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			dist[i][j]=10000;

    p=0;
    q=1;
    dist[x][y]=0;
    
	while(p<=q)
	{
		p++;
		x=xx[p];
		y=yy[p];

		for(int i=0;i<=7;i++)
		{
			x1=x+dx[i],y1=y+dy[i];
			if(viz[x1][y1]==0&&a[x1][y1]!='X'&&1<=x1&&n>=x1&&1<=y1&&m>=y1)
			{
				q++;
				xx[q]=x1;
				yy[q]=y1;
				viz[x1][y1]=1;
				dist[x1][y1]=dist[x][y]+1;
			}
		}

	}
	
}

int main()
{
	int rx=0,ry=0,jx=0,jy=0;
	char c;
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d %d\n",&n,&m);

	for(i=1;i<=n;i++)
	{
		fgets(s,110,stdin);
		
		for(j=1;j<=m;j++)
		{
		    c=s[j-1];
        	a[i][j]=c;
			if(c=='R')
            {
                rx=i;
                ry=j;
            }
			if(c=='J')
            {
                jx=i;
                jy=j;
            }
		}

	}

	df(rx,ry,R);
    df(jx,jy,J);
    
    int min=32000,e,r;
    
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(R[i][j]==J[i][j]&&R[i][j]<min)
            {
                min=R[i][j];
                e=i;
                r=j;
            }
    
    printf("%d %d %d",min+1,e,r);
    
    return 0;
}