Cod sursa(job #158941)

Utilizator ocneanusilviaocneanu silvia ilona ocneanusilvia Data 13 martie 2008 21:30:02
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include<fstream.h>
ifstream f("rj.in");
ofstream g("rj.out");
int const N=10000,K=8;
int r[101][101],ju[101][101],n,m,c[3][N],d[3][9],rl,rc,jl,jc,x,y,xv,yv,xp,yp,tmin;
char a[101][101];
int p,u;

void init_coada()
{
p=-1;
u=0;
}

int ver_plina()
{
if(u==0&&p==N-1)
	return 1;
else
	return 0;
}

int ver_vida()
{
if(p<u)
	return 1;
else
	return 0;
}

void adauga(int x,int y)
{
int i;
if(p<N-1)
	{p=p+1;
	c[1][p]=x;
	c[2][p]=y;
	}
else
	if(u!=0)
		{for(i=u;i<=p;i++)
			{c[1][i-u]=c[1][i];
			c[2][i-u]=c[2][i];
			}
		p=p-u;
		u=0;
		p=p+1;
		c[1][p]=x;
		c[2][p]=y;
		}
}

void elimina(int &x,int &y)
{
u=u+1;
x=c[1][u-1];
y=c[2][u-1];
}

/*void afisare()
{
int i;
for(i=p;i>=u;i--)
	cout<<"{"<<c[1][i]<<" "<<c[2][i]<<"} ";
cout<<endl;
}                             */


void citire()
{
int i,j;
d[1][1]=0;d[2][1]=1;
d[1][2]=1;d[2][2]=0;
d[1][3]=0;d[2][3]=-1;
d[1][4]=-1;d[2][4]=0;
d[1][5]=1;d[2][5]=1;
d[1][6]=1;d[2][6]=-1;
d[1][7]=-1;d[2][7]=-1;
d[1][8]=-1;d[2][8]=1;
char c;
f>>n;
f>>m;f.get();
for(i=1;i<=n;i++)
	{for(j=1;j<=m;j++)
		{f.get(c);
		if(c=='R')
			{rl=i;
			rc=j;
			}
		if(c=='J')
			{jl=i;
			jc=j;
			}
		a[i][j]=c;
		}
	f.get();
	}
/*
d[1][1]=0;d[2][1]=1;
d[1][2]=1;d[2][2]=0;
d[1][3]=0;d[2][3]=-1;
d[1][4]=-1;d[2][4]=0;*/
}

void julieta()
{
int k;
init_coada();
adauga(jl,jc);
ju[jl][jc]=1;
while(ver_vida()==0)
	{elimina(x,y);
	for(k=1;k<=8;k++)
		{xv=x+d[1][k];
		yv=y+d[2][k];
		if(xv>=1&&xv<=n&&yv>=1&&yv<=m)
			if(a[xv][yv]!='X'&&ju[xv][yv]==0)
				{ju[xv][yv]=ju[x][y]+1;
				adauga(xv,yv);
				}
		}
	}
}

void romeo()
{
int k;
init_coada();
adauga(rl,rc);
r[rl][rc]=1;
while(ver_vida()==0)
	{elimina(x,y);
	for(k=1;k<=8;k++)
		{xv=x+d[1][k];
		yv=y+d[2][k];
		if(xv>=1&&xv<=n&&yv>=1&&yv<=m)
			if(a[xv][yv]!='X'&&r[xv][yv]==0)
				{r[xv][yv]=r[x][y]+1;
				adauga(xv,yv);
				}
		}
	}
}

void verifica(int &tmin,int &xp,int &yp)
{
int i,j;
tmin=32000;
for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
		if(r[i][j]==ju[i][j]&&r[i][j]!=0)
			if(r[i][j]<tmin)
				{tmin=r[i][j];
				xp=i;
				yp=j;
				}
}

/*void afis_mat()
{
int i,j;
for(i=1;i<=n;i++)
	{for(j=1;j<=m;j++)
		g<<r[i][j]<<" ";
	g<<endl;
	}
g<<endl;
for(i=1;i<=n;i++)
	{for(j=1;j<=m;j++)
		g<<ju[i][j]<<" ";
	g<<endl;
	}
g<<endl;
}         */

int main()
{
citire();
f.close();
julieta();
romeo();
verifica(tmin,xp,yp);
g<<tmin<<" "<<xp<<" "<<yp;
g.close();
return 0;
}