Pagini recente » Cod sursa (job #2705486) | Cod sursa (job #2575277) | Cod sursa (job #1751538) | Cod sursa (job #2657962) | Cod sursa (job #1677803)
#include <fstream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
ifstream intrare("rj.in");
ofstream iesire("rj.out");
int vecini_x[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
int vecini_y[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
struct coord {
int x;
int y;
};
queue< coord > Q_r_j, Q_j_r;
vector< vector<int> > matrice_j_r, matrice_r_j;
coord dimensiune_matrice, romeo, julieta;
string linie;
int codificare_caracter(char c) {
switch (c) {
case 'X':
return -1;
case 'R':
return 1;
case 'J':
return 2;
case ' ':
return 0;
}
}
coord make_coord_struct(int x, int y) {
coord a;
a.x = x;
a.y = y;
return a;
}
void lee_j_r() {
Q_j_r.push(make_coord_struct(julieta.x, julieta.y));
while (!Q_j_r.empty()) {
int x = Q_j_r.front().x, y = Q_j_r.front().y;
Q_j_r.pop();
for (int v = 0; v < 8; v++) {
coord vecin;
vecin.x = x + vecini_x[v];
vecin.y = y + vecini_y[v];
if (matrice_j_r[vecin.x][vecin.y] == 0) {
matrice_j_r[vecin.x][vecin.y] = matrice_j_r[x][y] + 1;
Q_j_r.push(make_coord_struct(vecin.x, vecin.y));
if (vecin.x == romeo.x && vecin.y == romeo.y) return;
}
}
}
}
void lee_r_j() {
Q_r_j.push(make_coord_struct(romeo.x, romeo.y));
while (!Q_r_j.empty()) {
int x = Q_r_j.front().x, y = Q_r_j.front().y;
Q_r_j.pop();
for (int v = 0; v < 8; v++) {
coord vecin;
vecin.x = x + vecini_x[v];
vecin.y = y + vecini_y[v];
if (matrice_r_j[vecin.x][vecin.y] == 0) {
matrice_r_j[vecin.x][vecin.y] = matrice_r_j[x][y] + 1;
Q_r_j.push(make_coord_struct(vecin.x, vecin.y));
if (vecin.x == julieta.x && vecin.y == julieta.y) return;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
intrare >> dimensiune_matrice.x >> dimensiune_matrice.y;
matrice_j_r = matrice_r_j = vector< vector<int> >(dimensiune_matrice.x + 2, vector<int>(dimensiune_matrice.y + 2));
for (int i = 0; i < dimensiune_matrice.x + 1; i++) matrice_r_j[i][0] = matrice_j_r[i][0] = matrice_r_j[i][dimensiune_matrice.y + 1] = matrice_j_r[i][dimensiune_matrice.y + 1] = -1;
for (int j = 0; j < dimensiune_matrice.y + 1; j++) matrice_r_j[0][j] = matrice_j_r[0][j] = matrice_r_j[dimensiune_matrice.x + 1][j] = matrice_j_r[dimensiune_matrice.x + 1][j] = -1;
getline(intrare, linie);
for (int i = 1; i <= dimensiune_matrice.x; i++) {
getline(intrare, linie);
int j = 1;
for (char c : linie) {
int x = codificare_caracter(c);
if (!(x == 1 || x == 2))
matrice_r_j[i][j] = matrice_j_r[i][j] = x;
else if (x == 1) {
romeo.x = i;
romeo.y = j;
}
else {
julieta.x = i;
julieta.y = j;
}
j++;
}
}
matrice_r_j[romeo.x][romeo.y] = 1;
matrice_j_r[julieta.x][julieta.y] = 1;
lee_j_r();
lee_r_j();
int fin_x, fin_y, timp;
bool OK = true;
for (int j = 1; j <= dimensiune_matrice.y && OK; j++) {
for (int i = 1; i <= dimensiune_matrice.x; i++) {
if (matrice_r_j[i][j] == matrice_j_r[i][j] && (matrice_r_j[i][j] != -1 || matrice_j_r[i][j] != -1)) {
fin_x = i;
fin_y = j;
timp = matrice_j_r[i][j];
OK = false;
break;
}
}
}
iesire << timp << " " << fin_x << " " << fin_y;
}