Cod sursa(job #1677803)

Utilizator dancojocaru2000Dan Cojocaru dancojocaru2000 Data 6 aprilie 2016 19:59:16
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.2 kb
#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;
}