Cod sursa(job #2667277)

Utilizator ADINAIOANA-BORTAAdina Borta ADINAIOANA-BORTA Data 3 noiembrie 2020 11:39:14
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <queue>
#include <utility>

using namespace std;
const int NMAX = 101;
int rj[NMAX][NMAX][2], n, m;
queue<pair<int, int>> q;
int ox[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int oy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

bool valid(int acc, int x, int y) {
	return (x > 0 && y > 0 && x <= n && y <= m && rj[x][y][acc] == 0);
}

void BFS(int acc, int x, int y) {
	q.push(make_pair(x, y));
	while (!q.empty()) {
		int curr_x, curr_y, v_x, v_y;
		curr_x = q.front().first;
		curr_y = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++) {
			v_x = ox[i] + curr_x;
			v_y = oy[i] + curr_y;
			if (valid(acc, v_x, v_y)) {
				q.push(make_pair(v_x, v_y));
				rj[v_x][ v_y][acc] = rj[curr_x][curr_y][acc] + 1;
			}
		}
	}
	
}






int main() {
	ifstream in("rj.in");
	ofstream out("rj.out");

	int rx, ry, jx, jy, min=10000, pos_x, pos_y;
	in >> n >> m;

	in.get();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char x;
			x = in.get();
			if (x == 'R') {
				rx = i;
				ry = j;
				rj[i][j][0] = 1;
			}
			else if (x == 'J') {
				jx = i;
				jy = j;
				rj[i][j][1] = 1;

			}
			else if (x == 'X') {
				rj[i][j][0] = -1;
				rj[i][j][1] = -1;
			}
			else {
				rj[i][j][0] = 0;
				rj[i][j][1] = 0;
			}

		}
		in.get();
	}

	BFS(0, rx, ry);
	BFS(1, jx, jy);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (rj[i][j][0] == rj[i][j][1] && rj[i][j][1] < min && rj[i][j][1] > 0) {
				min = rj[i][j][1];
				pos_x = i;
				pos_y = j;
			}
		}
	}
	out << min << " " << pos_x << " " << pos_y;

	return 0;

}