Cod sursa(job #799126)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 17 octombrie 2012 23:34:10
Problema Rj Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 3.41 kb
#include<stdio.h>
FILE *f,*g;
int n,m,B[101][101],C[101][101],xR,yR,xJ,yJ,x,y,tmin,i,j,cx[10001],cy[10001],ps,pf,l,c;
char s[109],ch;
int main()
{
	f=fopen("rj.in","r");
	g=fopen("rj.out","w");
	fscanf(f,"%d %d \n",&n,&m);
	for(i=1;i<=n;i++)
	{
		fgets(s,114,f);
		for(j=0;j<m;j++)
		{
		    ch=s[j];
			if(ch=='X')
			{
				B[i][j+1]=-1;
				C[i][j+1]=-1;
			}
			if(ch=='R')
			{
				xR=i;
				yR=j+1;
			}
			if(ch=='J')
			{
				xJ=i;
				yJ=j+1;
			}
		}
	}
	//calculam matricea B pentru Romeo
	B[xR][yR]=1;
	cx[0]=xR;
	cy[0]=yR;
	ps=0;
	pf=0;
	while(ps<=pf)
	{
		l=cx[ps];
		c=cy[ps];
		//N
		if(l-1>=1 && B[l-1][c]==0)
		{
			B[l-1][c]=B[l][c]+1;
			pf++;
			cx[pf]=l-1;
			cy[pf]=c;
		}
		//NE
		if(l-1>=1 && c+1<=m && B[l-1][c+1]==0)
		{
			B[l-1][c+1]=B[l][c]+1;
			pf++;
			cx[pf]=l-1;
			cy[pf]=c+1;
		}
		//S
		if(l+1<=n && B[l+1][c]==0)
		{
			B[l+1][c]=B[l][c]+1;
			pf++;
			cx[pf]=l+1;
			cy[pf]=c;
		}
		//V
		if(c-1>=1 && B[l][c-1]==0)
		{
			B[l][c-1]=B[l][c]+1;
			pf++;
			cx[pf]=l;
			cy[pf]=c-1;
		}
		//E
		if(c+1<=m && B[l][c+1]==0)
		{
			B[l][c+1]=B[l][c]+1;
			pf++;
			cx[pf]=l;
			cy[pf]=c+1;
		}
		//SV
		if(l+1<=n && c-1>=1 && B[l+1][c-1]==0)
		{
			B[l+1][c-1]=B[l][c]+1;
			pf++;
			cx[pf]=l+1;
			cy[pf]=c-1;
		}
		//NV
		if(l-1>=1 && c-1>=1 && B[l-1][c-1]==0)
		{
			B[l-1][c-1]=B[l][c]+1;
			pf++;
			cx[pf]=l-1;
			cy[pf]=c-1;
		}
		//SE
		if(l+1<=n && c+1<=m && B[l+1][c+1]==0)
		{
			B[l+1][c+1]=B[l][c]+1;
			pf++;
			cx[pf]=l+1;
			cy[pf]=c+1;
		}
		ps++;
	}

	//calculam matricea C pentru Julieta
	C[xJ][yJ]=1;
	cx[0]=xJ;
	cy[0]=yJ;
	ps=0;
	pf=0;
	while(ps<=pf)
	{
		l=cx[ps];
		c=cy[ps];
		//N
		if(l-1>=1 && C[l-1][c]==0)
		{
			C[l-1][c]=C[l][c]+1;
			pf++;
			cx[pf]=l-1;
			cy[pf]=c;
		}
		//NE
		if(l-1>=1 && c+1<=m && C[l-1][c+1]==0)
		{
			C[l-1][c+1]=C[l][c]+1;
			pf++;
			cx[pf]=l-1;
			cy[pf]=c+1;
		}
		//S
		if(l+1<=n && C[l+1][c]==0)
		{
			C[l+1][c]=C[l][c]+1;
			pf++;
			cx[pf]=l+1;
			cy[pf]=c;
		}
		//V
		if(c-1>=1 && C[l][c-1]==0)
		{
			C[l][c-1]=C[l][c]+1;
			pf++;
			cx[pf]=l;
			cy[pf]=c-1;
		}
		//E
		if(c+1<=m && C[l][c+1]==0)
		{
			C[l][c+1]=C[l][c]+1;
			pf++;
			cx[pf]=l;
			cy[pf]=c+1;
		}
		//SV
		if(l+1<=n && c-1>=1 && C[l+1][c-1]==0)
		{
			C[l+1][c-1]=C[l][c]+1;
			pf++;
			cx[pf]=l+1;
			cy[pf]=c-1;
		}
		//NV
		if(l-1>=1 && c-1>=1 && C[l-1][c-1]==0)
		{
			C[l-1][c-1]=C[l][c]+1;
			pf++;
			cx[pf]=l-1;
			cy[pf]=c-1;
		}
		//SE
		if(l+1<=n && c+1<=m && C[l+1][c+1]==0)
		{
			C[l+1][c+1]=C[l][c]+1;
			pf++;
			cx[pf]=l+1;
			cy[pf]=c+1;
		}
		ps++;
	}
	/*CALCULAM MINIMUL*/
	tmin=m*n+1;
	x=n+1;
    y=m+1;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(B[i][j]==C[i][j] && B[i][j]>0 &&
                (B[i][j]<tmin ||
                 (B[i][j]==tmin && i<x) ||
                 (B[i][j]==tmin && i==x && j<y)
                )
              )
			{
				tmin=B[i][j];
				x=i;
				y=j;
			}
		}
	}
	fprintf(g,"%d %d %d",x,y,tmin);
    /*
	fprintf(g,"\n");
	for (i=1;i<=n;i++)
	{
	    for (j=1;j<=m;j++)
	    {
	        fprintf(g,"%3d ",B[i][j]);
	    }
	    fprintf(g,"\n");
	}
		fprintf(g,"\n");
	for (i=1;i<=n;i++)
	{
	    for (j=1;j<=m;j++)
	    {
	        fprintf(g,"%3d ",C[i][j]);
	    }
	    fprintf(g,"\n");
	}
    */
	fclose(f);
	fclose(g);
	return 0;
}