Pagini recente » Cod sursa (job #1647642) | Cod sursa (job #2551239) | Cod sursa (job #331966) | Cod sursa (job #547361) | Cod sursa (job #2666693)
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int nr, n;
char C;
int m, x, y;
int a[176][176],R[101][101],J[101][101];
struct pereche
{
int x, y ;
} start,stop;
int dx[]= {0, 0, 1, 0, -1, -1, 1, -1, 1};
int dy[]= {0, 1, 0, -1, 0, -1, 1, 1,-1};
queue < pereche > Q,T;
int interior ( int i, int j )
{
return i <= n and i >= 1 and j <= m and j >= 1 ;//daca se afla in matrice
}
void leeR ( pereche start )
{
int i = start.x;
int j = start.y;
R[i][j] = 1;
Q.push(start); // adaug in coada
while ( !Q.empty() ) // cat timp coada nu este vida
{
pereche varf = Q.front();
Q.pop();
i = varf.x;
j = varf.y; // extrag din coada varful cozii
for ( int k = 1; k <= 8; k++ )
{
int ox = i + dx[k];
int oy = j + dy[k]; //coordonatele vecinilor
if ( interior(ox,oy) and R[ox][oy] == 0 ) // daca vecinul se afla in matrice si pot ajunge la el
{
R[ox][oy] = R[i][j] + 1;
pereche vecin;
vecin.x = ox;
vecin.y = oy;
Q.push(vecin); // bag vecinii in coada
}
}
}
}
void leeJ ( pereche stop )
{
int i = stop.x;
int j = stop.y;
J[i][j] = 1;
T.push(stop); // adaug in coada
while ( !T.empty() ) // cat timp coada nu este vida
{
pereche varf = T.front();
T.pop();
i = varf.x;
j = varf.y; // extrag din coada varful cozii
for ( int k = 1; k <= 8; k++ )
{
int ox = i + dx[k];
int oy = j + dy[k]; //coordonatele vecinilor
if ( interior(ox,oy) and J[ox][oy] == 0 ) // daca vecinul se afla in matrice si pot ajunge la el
{
J[ox][oy] = J[i][j] + 1;
pereche vecin;
vecin.x = ox;
vecin.y = oy;
T.push(vecin); // bag vecinii in coada
}
}
}
}
char s[101];
int main()
{
f >> n >> m;
f.get();
for(int i = 1; i <= n; i++)
{
f.getline(s,101);
/// g << s <<endl;
for ( int j = 1; j <= m; j++ )
{
if ( s[j-1] == 'X' )
{
//marchez obstacolele
R[i][j] = -1;
J[i][j] = -1;
}
else if ( s[j-1] == 'R' )
{
//aflam coordonatele lui Romeo
start.x = i;
start.y = j;
R[i][j] = 0;
J[i][j] = -1;
}
else if ( s[j-1] == 'J' )
{
//aflam coordonatele Julietei
stop.x = i;
stop.y = j;
J[i][j] = 0;
R[i][j] = -1;
}
else
{
//altfell este zona de trecere
R[i][j] = 0;
J[i][j] = 0;
}
}
}
leeR(start); //aflam distantele minime pentru cazul in care se pleaca din coordonatele lui Romeo si se ajunge la cele ale Julietei
leeJ(stop); //aflam distantele minime pentru cazul in care se pleaca din coordonatele Julietei si se ajunge la cele ale lui Romeo
/// for(int i=1; i<=n; i++ and g<<endl) //afisam matricea lui Romeo
/// for(int j=1; j<=m; j++)
/// g<<R[i][j]<<" ";
/// for(int i=1; i<=n; i++ and g<<endl) //afisam matricea Julietei
/// for(int j=1; j<=m; j++)
/// g<<J[i][j]<<" ";
int minim = 99999999, ox=-1, oy=-1;
for ( int i = 1 ; i <= n ; i++ )
for (int j = 1 ; j <= m ; j++ )
if ( R[i][j] == J[i][j] and R[i][j] < minim and R[i][j] >0 ) ///daca s-a parcurs un nr egal de pasi si e minima distanta
{
minim = R[i][j] ;
ox = i ;
oy = j ;
}
g << minim << ' ' << ox << ' ' << oy << endl;
return 0;
}