Pagini recente » Cod sursa (job #59573) | Cod sursa (job #2654311) | Cod sursa (job #71826) | Cod sursa (job #2491015) | Cod sursa (job #2668486)
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int m,n,x,y, Romeo[105][105],Julieta[105][105],minim = 500000, loc_intalnire_x=-1, loc_intalnire_y=-1;
struct coordonate
{
int x, y ;
} romeo,julieta;
///vectori care ma ajuta sa ma deplasez in matrice
int directie_x[]= {0, 0, 1, 0, -1, -1, 1, -1, 1};
int directie_y[]= {0, 1, 0, -1, 0, -1, 1, 1,-1};
queue < coordonate > Q1,Q2;
///Functie care verifica daca ies din matrice
bool esteInMatrice ( int i, int j )
{
return i <= n && j <= m && i >= 1 && j >= 1 ;
}
void leeRomeo ( coordonate romeo )
{
///Pornesc din locul in care se afla Romeo initial
int i = romeo.x;
int j = romeo.y;
Romeo[i][j] = 1;
Q1.push(romeo);
while ( !Q1.empty() ) ///Cat timp coada nu este vida inseamna ca inca mai am unde sa ma duc in matrice
{
coordonate loc = Q1.front();
Q1.pop();
i = loc.x;
j = loc.y;
///Verific vecinii in toate directiile: sus,jos,stanga, dreapta si pe cei de pe diagonale
for ( int k = 1; k <= 8; k++ )
{
int vecin_x = i + directie_x[k]; ///Salvez coordonatele vecinilor
int vecin_y = j + directie_y[k];
if ( esteInMatrice(vecin_x,vecin_y) && Romeo[vecin_x][vecin_y] == 0 )
///Verific daca locul pe care vreau sa merg nu este un obstacol si ma asigur ca nu ies din matrice
{
Romeo[vecin_x][vecin_y] = Romeo[i][j] + 1;
///In matrice va ramane salvat lungimea drumului din locul de plecare pana in locul curent
coordonate vecin;
vecin.x = vecin_x;
vecin.y = vecin_y;
///Introduc in coada vecinii
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 loc = Q2.front();
Q2.pop();
i = loc.x;
j = loc.y;
for ( int k = 1; k <= 8; k++ )
{
int vecin_x = i + directie_x[k];
int vecin_y = j + directie_y[k];
if ( esteInMatrice(vecin_x,vecin_y) && Julieta[vecin_x][vecin_y] == 0 )
{
Julieta[vecin_x][vecin_y] = Julieta[i][j] + 1;
coordonate vecin;
vecin.x = vecin_x;
vecin.y = vecin_y;
Q2.push(vecin);
}
}
}
}
char linie[105];
int main()
{
f >> n >> m;
f.get();
for(int i = 1; i <= n; i++)
{
f.getline(linie,105);
///In matrici vom marca cu -1 obstacolele
///iar unde este spatiu de trecere va ramane 0 doarece matricile sunt declarate global
for ( int j = 1; j <= m; j++ )
{
if ( linie[j-1] == 'X' )
Romeo[i][j] = Julieta[i][j] = -1;
///Salvez coordonatele lui Romeo
if ( linie[j-1] == 'R' )
{
romeo.x = i;
romeo.y = j;
Julieta[i][j] = -1;
}
///Salvez coordonatele Julietei
if ( linie[j-1] == 'J' )
{
julieta.x = i;
julieta.y = j;
Romeo[i][j] = -1;
}
}
}
///Facem 2 Lee-uri separate pentru Romeo si Julieta
///Avem o matrice in care sunt salvate drumurile lui Romeo si una cu drumurile Julietei
leeRomeo(romeo);
leeJulieta(julieta);
for ( int i = 1 ; i <= n ; i++ )
for (int j = 1 ; j <= m ; j++ )
if ( Romeo[i][j] == Julieta[i][j] && Romeo[i][j] >0 )
///Caut locul de intalnire, adica locul pana unde fiecare a parcurs aceeasi distanta, iau cea mai mica valoare pe care o gasesc
{
minim = Romeo[i][j] ;
loc_intalnire_x = i ;
loc_intalnire_y = j ;
}
g << minim << ' ' << loc_intalnire_x << ' ' << loc_intalnire_y << endl;
return 0;
}