Pagini recente » Cod sursa (job #627234) | Cod sursa (job #2920625) | Cod sursa (job #2166088) | Cod sursa (job #800457) | Cod sursa (job #1481893)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
int f[120][120],r[120][120],j[120][120],k,i,m,x,xi,xu,mi,mu,xo,xc,mo,mc,ok,cmin,kmin,imin;
string g[120];
queue <int> rx,rm,jx,jm;
int main()
{
ifstream fin("rj.in");
ofstream fout("rj.out");
fin>>x>>m;
for(k=0;k<=x;k++)
getline(fin,g[k]);
for (k=1;k<=x;k++)
for (i=1;i<=m;i++)
r[k][i]=j[k][i]=x*m+2;
for(k=1;k<=x;k++)
{
for(i=0;i<m;i++)
{
if(g[k][i]=='X')
f[k][i+1]=1;
if(g[k][i]=='R')
{
r[k][i+1]=1;
xi=k;
mi=i+1;
}
if(g[k][i]=='J')
{
j[k][i+1]=1;
xo=k;
mo=i+1;
}
}
}
for(k=1;k<=x;k++)
f[k][0]=f[k][m+1]=1;
for(k=1;k<=m;k++)
f[0][k]=f[x+1][k]=1;
rx.push(xi); rm.push(mi);
jx.push(xo); jm.push(mo);
for(cmin=m*x+2;!rx.empty();)
{
xc=rx.front(); rx.pop();
mc=rm.front(); rm.pop();
xu=xc-1; mu=mc-1;
if(f[xu][mu]==0)
{
if(r[xu][mu]>=r[xc][mc]+2)
{
r[xu][mu]=r[xc][mc]+1;
rx.push(xu); rm.push(mu);
}
}
xu=xc-1; mu=mc+1;
if(f[xu][mu]==0)
{
if(r[xu][mu]>=r[xc][mc]+2)
{
r[xu][mu]=r[xc][mc]+1;
rx.push(xu); rm.push(mu);
}
}
xu=xc+1; mu=mc+1;
if(f[xu][mu]==0)
{
if(r[xu][mu]>=r[xc][mc]+2)
{
r[xu][mu]=r[xc][mc]+1;
rx.push(xu); rm.push(mu);
}
}
xu=xc+1; mu=mc-1;
if(f[xu][mu]==0)
{
if(r[xu][mu]>=r[xc][mc]+2)
{
r[xu][mu]=r[xc][mc]+1;
rx.push(xu); rm.push(mu);
}
}
xu=xc+1; mu=mc;
if(f[xu][mu]==0)
{
if(r[xu][mu]>=r[xc][mc]+2)
{
r[xu][mu]=r[xc][mc]+1;
rx.push(xu); rm.push(mu);
}
}
xu=xc-1; mu=mc;
if(f[xu][mu]==0)
{
if(r[xu][mu]>=r[xc][mc]+2)
{
r[xu][mu]=r[xc][mc]+1;
rx.push(xu); rm.push(mu);
}
}
xu=xc; mu=mc+1;
if(f[xu][mu]==0)
{
if(r[xu][mu]>=r[xc][mc]+2)
{
r[xu][mu]=r[xc][mc]+1;
rx.push(xu); rm.push(mu);
}
}
xu=xc; mu=mc-1;
if(f[xu][mu]==0)
{
if(r[xu][mu]>=r[xc][mc]+2)
{
r[xu][mu]=r[xc][mc]+1;
rx.push(xu); rm.push(mu);
}
}
}
for(;!jx.empty();)
{
xc=jx.front(); jx.pop();
mc=jm.front(); jm.pop();
xu=xc+1; mu=mc;
if(f[xu][mu]==0)
{
if(j[xu][mu]>=j[xc][mc]+2)
{
j[xu][mu]=j[xc][mc]+1;
jx.push(xu); jm.push(mu);
}
}
xu=xc-1; mu=mc;
if(f[xu][mu]==0)
{
if(j[xu][mu]>=j[xc][mc]+2)
{
j[xu][mu]=j[xc][mc]+1;
jx.push(xu); jm.push(mu);
}
}
xu=xc; mu=mc+1;
if(f[xu][mu]==0)
{
if(j[xu][mu]>=j[xc][mc]+2)
{
j[xu][mu]=j[xc][mc]+1;
jx.push(xu); jm.push(mu);
}
}
xu=xc; mu=mc-1;
if(f[xu][mu]==0)
{
if(j[xu][mu]>=j[xc][mc]+2)
{
j[xu][mu]=j[xc][mc]+1;
jx.push(xu); jm.push(mu);
}
}
xu=xc-1; mu=mc+1;
if(f[xu][mu]==0)
{
if(j[xu][mu]>=j[xc][mc]+2)
{
j[xu][mu]=j[xc][mc]+1;
jx.push(xu); jm.push(mu);
}
}
xu=xc-1; mu=mc-1;
if(f[xu][mu]==0)
{
if(j[xu][mu]>=j[xc][mc]+2)
{
j[xu][mu]=j[xc][mc]+1;
jx.push(xu); jm.push(mu);
}
}
xu=xc+1; mu=mc+1;
if(f[xu][mu]==0)
{
if(j[xu][mu]>=j[xc][mc]+2)
{
j[xu][mu]=j[xc][mc]+1;
jx.push(xu); jm.push(mu);
}
}
xu=xc+1; mu=mc-1;
if(f[xu][mu]==0)
{
if(j[xu][mu]>=j[xc][mc]+2)
{
j[xu][mu]=j[xc][mc]+1;
jx.push(xu); jm.push(mu);
}
}
}
for(k=1;k<=x;k++)
{
for(i=1;i<=m;i++)
{
fout.width(4);
fout<<r[k][i];
}
fout<<endl;
}
fout<<endl;fout<<endl;
for(k=1;k<=x;k++)
{
for(i=1;i<=m;i++)
{
fout.width(4);
fout<<j[k][i];
}
fout<<endl;
}
for(k=1;k<=x;k++)
{
for(i=1;i<=m;i++)
{
if(r[k][i]==j[k][i]&&r[k][i]<cmin)
{
cmin=r[k][i];
kmin=k;
imin=i;
}
}
}
fout<<cmin<<" "<<kmin<<" "<<imin<<endl;
return 0;
}