Cod sursa(job #1928185)

Utilizator robert_fanrRobert Banu robert_fanr Data 15 martie 2017 22:10:56
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
// RJ refacut.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <fstream>
#include <queue>
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 {
	short i, j;
	point() {}
	point(short i1, short j1) {
		i = i1;
		j = j1;
	}
}R,J;

short distR[105][105], distJ[105][105],
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 <point> q;

int main()
{
	in >> n >> m;
	in.get();
	for (short i = 0; i < n; ++i) {
		in.getline(linie, 101);
		for (short j = 0; j < m; ++j) {
			if (linie[j] == 'R') {
				R.i = i;
				R.j = j;
				distR[i][j] = 1;
				continue;
			}
			if (linie[j] == 'J') {
				J.i = i;
				J.j = 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()) {
		point curent = q.front();
		q.pop();
		for (short k = 1; k <= 9; ++k) {
			point nou(curent.i + iDirectie[k], curent.j + jDirectie[k]);
			if (nou.i >= 0 && nou.i < n && nou.j >= 0 && nou.j < m) {
				distR[nou.i][nou.j] = distR[curent.i][curent.j] + 1;
				q.push(nou);
			}
		}
	}

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

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

	//gasire punct intalnire
	point punctIntalnire;
	for (short i = 0; i<n; ++i)
		for (short 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.i = i + 1;
						punctIntalnire.j = j + 1;
					}
		}
	
	out << distMin << " " << punctIntalnire.i + 1 << " " << punctIntalnire.j;

	return 0;
}