Pagini recente » Cod sursa (job #941901) | Cod sursa (job #2891403) | Cod sursa (job #3273473) | Cod sursa (job #2485423) | Cod sursa (job #560332)
Cod sursa(job #560332)
#include<cstdio>
const int N=1<<7;
const int dx[]={-1,-1,0,1,1,1,0,-1};
const int dy[]={0,1,1,1,0,-1,-1,-1};
char s[N][N];
int nn,x[N*N],y[N*N],x1[N*N],y1[N*N],n,m,romeo[N][N],julieta[N][N];
void lee(int xx,int yy)
{
for (int i=0;i<8;i++)
{
int d1=xx+dx[i],d2=yy+dy[i];
if (d1>=0 && d1<n && d2>=0 && d2<m && romeo[d1][d2]==-1 && s[d1][d2]!='X')
{
nn++;
x1[nn]=d1;
y1[nn]=d2;
romeo[d1][d2]=romeo[xx][yy]+1;
}
}
}
void leej(int xx,int yy)
{
for (int i=0;i<8;i++)
{
int d1=xx+dx[i],d2=yy+dy[i];
if (d1>=0 && d1<n && d2>=0 && d2<m && julieta[d1][d2]==-1 && s[d1][d2]!='X')
{
nn++;
x1[nn]=d1;
y1[nn]=d2;
julieta[d1][d2]=julieta[xx][yy]+1;
}
}
}
void init()
{
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
{
romeo[i][j]=-1;
julieta[i][j]=-1;
}
}
int main()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
int xr,yr,xj,yj;
scanf("%d%d\n",&n,&m);
for (int i=0;i<n;i++)
{
gets(s[i]);
for (int j=0;j<m;j++)
if (s[i][j]=='R')
{
xr=i;
yr=j;
}
else
if (s[i][j]=='J')
{
xj=i;
yj=j;
}
}
init();
int nr=1;
x[1]=xr;
y[1]=yr;
romeo[xr][yr]=0;
while (nr)
{
nn=0;
for (int i=1;i<=nr;i++)
lee(x[i],y[i]);
nr=nn;
for (int i=1;i<=nr;i++)
{
x[i]=x1[i];
y[i]=y1[i];
}
}
nr=1;
x[1]=xj;
y[1]=yj;
julieta[xj][yj]=0;
while (nr)
{
nn=0;
for (int i=1;i<=nr;i++)
leej(x[i],y[i]);
nr=nn;
for (int i=1;i<=nr;i++)
{
x[i]=x1[i];
y[i]=y1[i];
}
}
int timp=N*N*N,xxx,yyy;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (romeo[i][j]==julieta[i][j] && romeo[i][j]<timp && s[i][j]!='X' && romeo[i][j]!=-1)
{
timp=romeo[i][j];
xxx=i;
yyy=j;
}
printf("%d %d %d\n",timp+1,xxx+1,yyy+1);
return 0;
}