Pagini recente » Cod sursa (job #678618) | Cod sursa (job #1606550) | Cod sursa (job #1581268) | Cod sursa (job #1009352) | Cod sursa (job #1597427)
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
std::ifstream fin("rj.in");
std::ofstream fout("rj.out");
int MapRomeo[128][128]; //Harta Romeo
int MapJulieta[128][128]; //Harta Julieta
int n, m; //Linii, Coloane
int romeoI, romeoJ, julietaI, julietaJ; //Coordonate Romeo, Julieta
std::queue <std::pair < int, int > > Coada; //Coada
const int di[] = {0, 0, 1, -1, 1, 1, -1, -1}; //Deplasare pe i
const int dj[] = {1, -1, 0, 0, 1, -1, 1, -1}; //Deplasare pe j
int coord_i, coord_j, coord_timp = (int)2e9; //Coordonatele finale si timpul dupa care se intalnesc
bool okRomeo(int x, int y) //Verificarea celulei daca este libera
{
if (x < 0 || y < 0 || x >= n || y >= m)
return false;
if (MapRomeo[x][y] == -1)
return false;
return true;
}
bool okJulieta(int x, int y)
{
if (x < 0 || y < 0 || x >= n || y >= m)
return false;
if (MapJulieta[x][y] == -1)
return false;
return true;
}
void LeeJulieta()
{
int i, j, iUrmator, jUrmator;
MapJulieta[julietaI][julietaJ] = 1; //Plec de la pozitia Julietei
Coada.push(std::make_pair(julietaI, julietaJ)); //Adaug pozitia Julietei in coada
while (!Coada.empty()) //Cat timp coada e goala
{
i = Coada.front().first; //Extrag coordonata i a primului element din coada
j = Coada.front().second; //Extrag coordonata j a primului element din coada
Coada.pop(); //Elimin elementul din coada
for (int directie = 0; directie < 8; directie++) //Verific toate pozitiile alaturate
{
iUrmator = i + di[directie]; //Coordonata i a pozitiei urmatoare
jUrmator = j + dj[directie]; //Coordonata j a pozitiei urmatoare
if (okJulieta(iUrmator, jUrmator) && MapJulieta[iUrmator][jUrmator] == 0) //Verific daca e o mutare valida
{
MapJulieta[iUrmator][jUrmator] = MapJulieta[i][j] + 1; //Incrementez valoarea pozitiei urmatoare
Coada.push(std::make_pair(iUrmator, jUrmator)); //Adaug in coada
}
}
}
}
void LeeRomeo()
{
int i, j, iUrmator, jUrmator;
MapRomeo[romeoI][romeoJ] = 1; //Plec de la pozitia lui Romeo
Coada.push(std::make_pair(romeoI, romeoJ)); //Adaug pozitia lui Romeo in coada
while (!Coada.empty()) //Cat timp coada e goala
{
i = Coada.front().first; //Extrag coordonata i a primului element din coada
j = Coada.front().second; //Extrag coordonata j a primului element din coada
Coada.pop(); //Elimin elementul din coada
for (int directie = 0; directie < 8; directie++) //Verific toate pozitiile alaturate
{
iUrmator = i + di[directie]; //Coordonata i a pozitiei urmatoare
jUrmator = j + dj[directie]; //Coordonata j a pozitiei urmatoare
if (okRomeo(iUrmator, jUrmator) && MapRomeo[iUrmator][jUrmator] == 0) //Verific daca e o mutare valida
{
MapRomeo[iUrmator][jUrmator] = MapRomeo[i][j] + 1; //Incrementez valoarea pozitiei urmatoare
Coada.push(std::make_pair(iUrmator, jUrmator)); //Adaug in coada
}
}
}
}
void Read() //Construirea hartii
{
fin >> n >> m; //Citesc liniile si coloanele
std::string aux;
std::getline(fin, aux, '\n'); //Trec la matrice
for (int i = 0; i < n; i++) //Parcurg liniile
{
std::getline(fin, aux, '\n'); //Citesc o intreaga liniile
for (int j = 0; j < m; j++) //Parcurg fiecare coloana
{
if (aux[j] == 'R')
{
//Initializez coordonatele lui Romeo
romeoI = i;
romeoJ = j;
//Initializez valoarea pozitiei
MapRomeo[i][j] = 0;
MapJulieta[i][j] = 0;
}
else if (aux[j] == 'J')
{
//Initializez coordonatele Julietei
julietaI = i;
julietaJ = j;
//Initializez valoarea pozitiei
MapRomeo[i][j] = 0;
MapJulieta[i][j] = 0;
}
else if (aux[j] == 'X')
{
MapRomeo[i][j] = -1;
MapJulieta[i][j] = -1;
}
else
{
MapRomeo[i][j] = 0;
MapJulieta[i][j] = 0;
}
}
}
}
void Cautare()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if ((MapRomeo[i][j] == MapJulieta[i][j]) && MapRomeo[i][j] > 0)
{
if (coord_timp >= MapRomeo[i][j] - 1)
{
coord_timp = MapRomeo[i][j];
coord_i = i + 1;
std::cout << j;
coord_j = j + 1;
}
}
}
}
fout << coord_timp << " " << coord_i << " " << coord_j;
}
int main(int argc, char *argv[])
{
Read(); //Construieste harta
LeeRomeo(); //Parcurere Lee pentru Romeo
LeeJulieta(); //Parcurgere Lee pentru Julieta
Cautare();
return 0;
}