Pagini recente » Cod sursa (job #354239) | Cod sursa (job #1737193) | Cod sursa (job #3124327) | Cod sursa (job #543841) | Cod sursa (job #156834)
Cod sursa(job #156834)
#include<fstream.h>
ifstream f("rj.in");
ofstream g("rj.out");
int const N=5000,K=8;
int r[101][101],ju[101][101],n,m,far 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;
return 0;
g.close();
}