Cod sursa(job #1928243)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 15 martie 2017 23:03:24
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb

// RJ refacut.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <fstream>
#include <queue>
#include <utility>
using namespace std;

ifstream in("rj.in");
ofstream out("rj.out");

int iDirectie[9] = { 0, -1, -1, -1,  0,  1,  1,  1,  0 };
int jDirectie[9] = { 0, -1,  0,  1,  1,  1,  0, -1, -1 };

/*struct point {
	int i, j;
	point() {}
	point(int i1, int j1) {
		i = i1;
		j = j1;
	}
}R,J;
*/
pair <int,int> R, J;

int distR[50][50], distJ[50][50],
di[9] = { -1,-1,-1, 0, 1, 1, 1, 0 },
dj[9] = { -1, 0, 1, 1, 1, 0,-1,-1 },
n, m, distMin = 32767;

char linie[105];

queue <pair<int,int>> q;

int main()
{
	in >> n >> m;
	in.get();
	for (int i = 0; i < n; ++i) {
		in.getline(linie, 101);
		for (int j = 0; j < m; ++j) {
			if (linie[j] == 'R') {
				R.first = i;
				R.second = j;
				distR[i][j] = 1;
				continue;
			}
			if (linie[j] == 'J') {
				J.first = i;
				J.second = j;
				distJ[i][j] = 1;
				continue;
			}
			if (linie[j] == 'X')
				distR[i][j] = distJ[i][j] = 32767;
		}
	}

	//BFS Romeo;
	q.push(R);

	while (!q.empty()) {
		pair <int,int> curent = q.front();
		q.pop();
		for (int k = 1; k <= 9; ++k) {
			pair<int,int> nou(curent.first + iDirectie[k], curent.second + jDirectie[k]);
			if (nou.first >= 0 && nou.first < n && nou.second >= 0 && nou.second < m) {
				distR[nou.first][nou.second] = distR[curent.first][curent.second] + 1;
				q.push(nou);
			}
		}
	}

	//BFS Julieta;
	q.push(J);

	while (!q.empty()) {
		pair <int,int> curent = q.front();
		q.pop();
		for (int k = 1; k <= 9; ++k) {
			pair <int,int> nou(curent.first + iDirectie[k], curent.second + jDirectie[k]);
			if (nou.first >= 0 && nou.first < n && nou.second >= 0 && nou.second < m) {
				distJ[nou.first][nou.second] = distJ[curent.first][curent.second] + 1;
				q.push(nou);
			}
		}
	}

	//gasire punct intalnire
	pair<int,int> punctIntalnire;
	for (int i = 0; i<n; ++i)
		for (int j = 0; j<m; ++j) {
			if (distR[i][j] != 0)
				if (distR[i][j] == distJ[i][j])
					if (distR[i][j] < distMin) {
						distMin = distR[i][j];
						punctIntalnire.first = i + 1;
						punctIntalnire.second = j + 1;
					}
		}

	out << distMin << " " << punctIntalnire.first + 1 << " " << punctIntalnire.second;

	return 0;
}