Cod sursa(job #500384)

Utilizator bumble.beeBuhai Diana bumble.bee Data 11 noiembrie 2010 23:39:42
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
# include <fstream.h>
# include <string.h>
# include <stdio.h>
int a[101][101],n,m,i,j,x1,y_1,x2,y2,p,u,ok,xm,ym,xn,nn,q,w,b[101][100];
typedef struct {int x,y;} COADA;
COADA Q[11000];
int dx[]={0,-1,0,1,0,-1,1,1,-1};
int dy[]={0,0,1,0,-1,1,1,-1,-1};

int interior (int q,int w)
{	if (q>=1 && q<=n && w>=1 && w<=n) return 1;
	else return 0;
}

int Lee2 ()
{	p=u=1;
	Q[u].x=x2;Q[u].y=y2;b[x2][y2]=1;ok=0;
	while (p<=u && ok==0)
	{	xm=Q[p].x;ym=Q[p].y;
		for (i=1;i<=8;i++)
		{	xn=xm+dx[i];
			nn=ym+dy[i];
			if (interior (xn,nn)==1 && b[xn][nn]==0)
			{	b[xn][nn]=b[xm][ym]+1;
				Q[++u].x=xn;Q[u].y=nn;
				if (xn==x1 && nn==y_1) ok=1;
			}
		}
		p++;
	}
	return b[x1][y_1];
}

/*void prcg()
{	o=x2;r=y2;
	while (o!=x1 && r!=y_1)
	{	Q[++k].x=o;Q[k].y=r;
		for (i=1;i<=8;i++)
		{	xn=o+dx[i];
			nn=r+dy[i];
			if (a[o][r]==(a[xn][nn]+1))
			{o=xn;r=nn;
			break;
			}
		}
	}
	k2=(k+1)/2;
	g<<Q[k2].x<<" "<<Q[k2].y<<" "<<k/k2;
	g.close();
}

int interior (int q,int w)
{	if (q>=1 && q<=n && w>=1 && w<=n) return 1;
	else return 0;
}*/

int Lee()
{	
	p=u=1;
	Q[u].x=x1;Q[u].y=y_1;a[x1][y_1]=1;ok=0;
	while (p<=u && ok==0)
	{	xm=Q[p].x;ym=Q[p].y;
		for (i=1;i<=8;i++)
		{	xn=xm+dx[i];
			nn=ym+dy[i];
			if (interior (xn,nn)==1 && a[xn][nn]==0)
			{	a[xn][nn]=a[xm][ym]+1;
				Q[++u].x=xn;Q[u].y=nn;
				if (xn==x2 && nn==y2) ok=1;
			}
		}
		p++;
	}
	return a[x2][y2];
}

int main ()
{	ifstream f("rj.in");
	ofstream g("rj.out");
	//ofstream g("rj.out");
	char s[101];
	f>>n>>m;
	for (i=1;i<=n+1;i++)
	{	f.getline(s,101);
		if (i!=1){
		for (j=0;j<=m;j++)
			if (s[j]==' ') a[i-1][j+1]=a[i-1][j+1]=0;
			else if (s[j]=='R') {a[i-1][j+1]=0;x1=i;y_1=j;b[i-1][j+1]=0;}
			else if (s[j]=='J') {a[i-1][j+1]=0;x2=i;y2=j;b[i-1][j+1]=0;}
			else if (s[j]=='X') {a[i-1][j+1]=1;b[i-1][j+1]=1;}
		}
	}
	x1=x1-1;y_1=y_1+1;
	x2=x2-1;y2=y2+1;
	i=Lee ();
	j=Lee2 ();ok=0;g<<(1+j)/2<<" ";
	for (i=1;i<=n;i++)
	{	for (j=1;j<=m;j++)
			if (a[i][j]==b[i][j] && a[i][j]!=1 && a[i][j]!=0) {g<<i<<" "<<j;ok=1;break;} 
		if (ok) break;
	}
	/*g<<'\n';
	for (i=1;i<=n;i++)
	{	for (j=1;j<=m;j++)
			g<<a[i][j]<<" ";
		g<<'\n';
	}g<<'\n';
	for (i=1;i<=n;i++)
	{	for (j=1;j<=m;j++)
			g<<b[i][j]<<" ";
		g<<'\n';
	}*/
	//g<<i<<" "<<j;
	f.close ();
	g.close ();
	return 0;
}