Pagini recente » Cod sursa (job #64772) | Cod sursa (job #1871740) | con | Cod sursa (job #1362267) | Cod sursa (job #2668626)
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
struct coordonate
{
int x, y ;
} romeo,julieta,intalnire;
int m, x, y,nr,n,minim = 99999999;
int Romeo[101][101],Julieta[101][101];
int dx[]= {0, 0, 1, 0, -1, -1, 1, -1, 1};
int dy[]= {0, 1, 0, -1, 0, -1, 1, 1,-1};
queue < coordonate > Q1,Q2;
bool esteInMatrice ( int i, int j )
{
return i <= n && i >= 1 && j <= m && j >= 1 ;
}
void leeRomeo ( coordonate romeo )
{
int i = romeo.x;
int j = romeo.y;
Romeo[i][j] = 1;
Q1.push(romeo);
while ( !Q1.empty() )
{
coordonate varf = Q1.front();
Q1.pop();
i = varf.x;
j = varf.y;
for ( int k = 1; k <= 8; k++ )
{
int ox = i + dx[k];
int oy = j + dy[k];
if ( esteInMatrice(ox,oy) && Romeo[ox][oy] == 0 )
{
Romeo[ox][oy] = Romeo[i][j] + 1;
coordonate vecin;
vecin.x = ox;
vecin.y = oy;
Q1.push(vecin);
}
}
}
}
void leeJulieta ( coordonate julieta )
{
int i = julieta.x;
int j = julieta.y;
Julieta[i][j] = 1;
Q2.push(julieta);
while ( !Q2.empty() )
{
coordonate varf = Q2.front();
Q2.pop();
i = varf.x;
j = varf.y;
for ( int k = 1; k <= 8; k++ )
{
int ox = i + dx[k];
int oy = j + dy[k];
if ( esteInMatrice(ox,oy) && Julieta[ox][oy] == 0 )
{
Julieta[ox][oy] = Julieta[i][j] + 1;
coordonate vecin;
vecin.x = ox;
vecin.y = oy;
Q2.push(vecin);
}
}
}
}
char linie[101];
int main()
{
f >> n >> m;
f.get();
for(int i = 1; i <= n; i++)
{
f.getline(linie,101);
for ( int j = 0; j <m; j++ )
{
if ( linie[j] == 'X' )
{
Romeo[i][j+1] = -1;
Julieta[i][j+1] = -1;
}
if ( linie[j] == 'R' )
{
romeo.x = i;
romeo.y = j+1;
Julieta[i][j+1] = -1;
}
if ( linie[j] == 'J' )
{
julieta.x = i;
julieta.y = j+1;
Romeo[i][j+1] = -1;
}
}
}
leeRomeo(romeo);
leeJulieta(julieta);
intalnire.x=-1, intalnire.y=-1;
for ( int i = 1 ; i <= n ; i++ )
for (int j = 1 ; j <= m ; j++ )
if ( Romeo[i][j] == Julieta[i][j] && Romeo[i][j] < minim && Romeo[i][j] >0 )
{
minim = Romeo[i][j] ;
intalnire.x= i ;
intalnire.y = j ;
}
g << minim << " " << intalnire.x << " " << intalnire.y << endl;
return 0;
}