Pagini recente » Cod sursa (job #947284) | Cod sursa (job #850648) | Cod sursa (job #3169294) | Cod sursa (job #3277922) | Cod sursa (job #1677437)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
char mm[101][101];
int R[101][101],J[101][101];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n,m;
int xR, yR, xJ, yJ, tmin=10000, a, b;
struct Element
{
int l,c,d;
};
Element x,y;
queue <Element> Q;
void Romeo(int x0, int y0)
{
x.l=xR;
x.c=yR;
R[x0][y0]=0;
Q.push(x);
while(!Q.empty())
{
x=Q.front();
Q.pop();
for(int k=0;k<4;k++)
{
y.l=x.l+dx[k];
y.c=x.c+dy[k];
if(R[y.l][y.c]==-2)
{
y.d=x.d+1;
R[y.l][y.c]=y.d;
Q.push(y);
}
}
}
/*for(int i=1; i<=n; i++)
{
for(int j=0; j<n; j++)
cout<<R[i][j]<<' ';
cout<<endl;
}
cout<<endl;*/
}
void Julieta(int x0, int y0)
{
while(!Q.empty())
Q.pop();
x.l=x.c=x.d=0;
y.l=y.c=y.d=0;
x.l=xJ;
x.c=yJ;
J[x0][y0]=0;
Q.push(x);
while(!Q.empty())
{
x=Q.front();
Q.pop();
for(int k=0;k<4;k++)
{
y.l=x.l+dx[k];
y.c=x.c+dy[k];
if(J[y.l][y.c]==-2)
{
y.d=x.d+1;
J[y.l][y.c]=y.d;
Q.push(y);
}
}
}
/*for(int i=1; i<=n; i++)
{
for(int j=0; j<n; j++)
cout<<J[i][j]<<' ';
cout<<endl;
}*/
}
int main()
{
in>>n>>m;
int i,j;
for(i=0;i<=n;i++)
in.getline(mm[i],100);
for(i=0;i<=n;i++)
for(j=0;j<m;j++)
if(mm[i][j]=='X')
{
J[i][j]=-1;
R[i][j]=-1;
}
else
{
if(mm[i][j]=='R')
{
xR=i;
yR=j;
J[i][j]=-2;
R[i][j]=0;
}
else
if(mm[i][j]=='J')
{
xJ=i;
yJ=j;
J[i][j]=0;
R[i][j]=-2;
}
else
if(mm[i][j]==' ')
{
R[i][j]=-2;
J[i][j]=-2;
}
}
Romeo(xR, yR);
Julieta(xJ,yJ);
for(i=1;i<=n;i++)
for(j=0;j<m;j++)
if (R[i][j]==J[i][j] && R[i][j]!=-1 && R[i][j]!=-2 && R[i][j]!=0)
if(R[i][j]<tmin)
{
tmin=R[i][j];
a=i;
b=j+1;
}
out<<tmin<<' '<<a<<' '<<b;
return 0;
}