Pagini recente » Cod sursa (job #1932425) | Cod sursa (job #136375) | Cod sursa (job #1933546) | Cod sursa (job #2218538) | Cod sursa (job #1372868)
#include <iostream>
#include<fstream>
#include<queue>
#include<string.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
queue <int> qx;
queue <int> qy;
char a[102][102];
char v[]=" .";
int b[102][102];
int main()
{
int n,m,i,j,tmin=32000,tx,ty,x,y,xr,yr,xj,yj;
f>>n>>m;
f.get();
for(i=1;i<=n;i++)
{
f.get(a[i],m+1);
strcat(a[i],v);
f.get();
}
for(i=1;i<=n;i++)
for(j=0;j<m;j++)
{
if(a[i][j]==' ')b[i][j+1]=-1;
else if(a[i][j]=='X')b[i][j+1]=-2;
else if(a[i][j]=='R'){b[i][j+1]=0; xr=i; yr=j;}
else if(a[i][j]=='J'){b[i][j+1]=0; xj=i; yj=j;}
}
for(i=0;i<=n+1;i++)
{
b[i][0]=-2;
b[i][m+1]=-2;
}
for(i=0;i<=m+1;i++)
{
b[0][i]=-2;
b[n+1][i]=-2;
}
qx.push(xr); qy.push(yr+1);
while(qx.empty()!=true)
{
x=qx.front(); y=qy.front();
if(b[x-1][y]==-1||b[x-1][y]>b[x][y]+1){b[x-1][y]=b[x][y]+1; qx.push(x-1); qy.push(y);}
if(b[x-1][y+1]==-1||b[x-1][y+1]>b[x][y]+1){b[x-1][y+1]=b[x][y]+1; qx.push(x-1); qy.push(y+1);}
if(b[x][y+1]==-1||b[x][y+1]>b[x][y]+1){b[x][y+1]=b[x][y]+1; qx.push(x); qy.push(y+1);}
if(b[x+1][y+1]==-1||b[x+1][y+1]>b[x][y]+1){b[x+1][y+1]=b[x][y]+1; qx.push(x+1); qy.push(y+1);}
if(b[x+1][y]==-1||b[x+1][y]>b[x][y]+1){b[x+1][y]=b[x][y]+1; qx.push(x+1); qy.push(y);}
if(b[x+1][y-1]==-1||b[x+1][y-1]>b[x][y]+1){b[x+1][y-1]=b[x][y]+1; qx.push(x+1); qy.push(y-1);}
if(b[x][y-1]==-1||b[x][y-1]>b[x][y]+1){b[x][y-1]=b[x][y]+1; qx.push(x); qy.push(y-1);}
if(b[x-1][y-1]==-1||b[x-1][y-1]>b[x][y]+1){b[x-1][y-1]=b[x][y]+1; qx.push(x-1); qy.push(y-1);}
qx.pop(); qy.pop();
}
qx.push(xj); qy.push(yj+1);
while(qx.empty()!=true)
{
x=qx.front(); y=qy.front();
i=x-1; j=y;
if(b[x-1][y]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
else if(i==tx)if(j<ty){tx=i;ty=j;}}}
else if(b[x-1][y]>b[x][y]+1){b[x-1][y]=b[x][y]+1; qx.push(x-1); qy.push(y);}
i=x-1; j=y+1;
if(b[x-1][y+1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
else if(i==tx)if(j<ty){tx=i;ty=j;}}}
else if(b[x-1][y+1]>b[x][y]+1){b[x-1][y+1]=b[x][y]+1; qx.push(x-1); qy.push(y+1);}
i=x; j=y+1;
if(b[x][y+1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
else if(i==tx)if(j<ty){tx=i;ty=j;}}}
else if(b[x][y+1]>b[x][y]+1){b[x][y+1]=b[x][y]+1; qx.push(x); qy.push(y+1);}
i=x+1; j=y+1;
if(b[x+1][y+1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
else if(i==tx)if(j<ty){tx=i;ty=j;}}}
else if(b[x+1][y+1]>b[x][y]+1){b[x+1][y+1]=b[x][y]+1; qx.push(x+1); qy.push(y+1);}
i=x+1; j=y;
if(b[x+1][y]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
else if(i==tx)if(j<ty){tx=i;ty=j;}}}
else if(b[x+1][y]>b[x][y]+1){b[x+1][y]=b[x][y]+1; qx.push(x+1); qy.push(y);}
i=x+1; j=y-1;
if(b[x+1][y-1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
else if(i==tx)if(j<ty){tx=i;ty=j;}}}
else if(b[x+1][y-1]>b[x][y]+1){b[x+1][y-1]=b[x][y]+1; qx.push(x+1); qy.push(y-1);}
i=x; j=y-1;
if(b[x][y-1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
else if(i==tx)if(j<ty){tx=i;ty=j;}}}
else if(b[x][y-1]>b[x][y]+1){b[x][y-1]=b[x][y]+1; qx.push(x); qy.push(y-1);}
i=x-1; j=y-1;
if(b[x-1][y-1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
else if(i==tx)if(j<ty){tx=i;ty=j;}}}
else if(b[x-1][y-1]>b[x][y]+1){b[x-1][y-1]=b[x][y]+1; qx.push(x-1); qy.push(y-1);}
qx.pop(); qy.pop();
}
g<<tmin+1<<" "<<tx<<" "<<ty;
return 0;
}