Pagini recente » Cod sursa (job #222076) | Cod sursa (job #1279891) | Diferente pentru utilizator/djok intre reviziile 96 si 95 | Monitorul de evaluare | Cod sursa (job #2712912)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
struct Nod
{
int x;
int y;
};
ifstream in("rj.in");
ofstream out("rj.out");
int n,m,x_r,y_r,x_j,y_j,poz_x,poz_y;
int mat_r[105][105],mat_j[105][105],mini=100000000;
void bordare(int n, int m)
{
for(int i=0; i<=n+1; i++)
{
mat_r[i][0]=-1;
mat_r[i][m+1]=-1;
mat_j[i][0]=-1;
mat_j[i][m+1]=-1;
}
for(int j=0; j<=m+1; j++)
{
mat_r[0][j]=-1;
mat_r[n+1][j]=-1;
mat_j[0][j]=-1;
mat_j[n+1][j]=-1;
}
}
int x[4]= {1,-1,0,0};
int y[4]= {0,0,1,-1};
void lee_r()
{
queue<Nod>q;
Nod w;
w.x=x_r;
w.y=y_r;
q.push(w);
while(!q.empty())
{
Nod nod;
nod=q.front();
q.pop();
if(nod.x == x_j && nod.y == y_j)
{
return;
}
for(int i=0; i<4; i++)
{
if( mat_r[nod.x + x[i]][nod.y + y[i]]==0)
{
Nod add;
add.x = nod.x + x[i];
add.y = nod.y + y[i];
mat_r[nod.x+ x[i]][nod.y+ y[i]]=mat_r[nod.x][nod.y]+1;
q.push(add);
}
}
}
}
void lee_j()
{
queue<Nod>q;
Nod w;
w.x=x_j;
w.y=y_j;
q.push(w);
while(!q.empty())
{
Nod nod;
nod=q.front();
q.pop();
// cout<<nod.x<<" "<<nod.y<<" \n";
// cout<<mat_j[nod.x][nod.y]<<" "<<mat_r[nod.x][nod.y]<<"\n\n";
if(nod.x == x_r && nod.y == y_r)
{
return;
}
if(mat_j[nod.x][nod.y]==mat_r[nod.x][nod.y])
{
if(mini>mat_j[nod.x][nod.y])
{
mini=mat_j[nod.x][nod.y];
poz_x=nod.x;
poz_y=nod.y;
}
}
for(int i=0; i<4; i++)
{
if( mat_j[nod.x + x[i]][nod.y + y[i]]==0)
{
Nod add;
add.x = nod.x + x[i];
add.y = nod.y + y[i];
mat_j[nod.x+ x[i]][nod.y+ y[i]]=mat_j[nod.x][nod.y]+1;
q.push(add);
}
}
}
}
int main()
{
in>>n>>m;
char c,p[105];
in.getline(p,104);
for(int i=1; i<=n; i++)
{
in.getline(p,104);
for(int j=1; j<=m; j++)
{
c=p[j-1];
if(c=='X')
{
mat_r[i][j]=-1;
mat_j[i][j]=-1;
}
else if(c=='R')
{
x_r=i;
y_r=j;
mat_r[i][j]=1;
}
else if(c=='J')
{
x_j=i;
y_j=j;
mat_j[i][j]=1;
}
}
}
bordare(n,m);
lee_r();
lee_j();
out<<mini-1<<" "<<poz_x<<" "<<poz_y;
return 0;
}