Cod sursa(job #1896610)

Utilizator robert_fanrRobert Banu robert_fanr Data 28 februarie 2017 19:49:09
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
// Rj infoarena.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <list>
//#include <limits>
#include <cstdio>
using namespace std;

ifstream in("rj.in"); //a se inlatura txt la final
ofstream out("rj.out");

const int N_MAX = 1002;
char matrice[N_MAX][N_MAX];
int n, m;

int distR[N_MAX][N_MAX], distJ[N_MAX][N_MAX]; //in astea vom calcula distanta de la rom/jul la fiecare punct liber

struct punct {
	int i, j;
} rom, jul;

void citire() {
	FILE * in_h = fopen("rj.in","r");
	//FILE ** pointer = &in_h;
	//fopen_s(pointer, "rj.in", "r");
	char trash;
	fscanf(in_h,"%d %d", &n, &m);
	int i, j;
	for (i = 1; i <= n; i++) {
		fscanf(in_h, "%c", &trash);
		for (j = 1; j <= m; j++) {
			fscanf(in_h, "%c", &matrice[i][j]);
			if (matrice[i][j] == 'R') {
				rom.i = i; rom.j = j; //aici se afla Romeo
			}
			if (matrice[i][j] == 'J') {
				jul.i = i; jul.j = j; //aici se afla Julieta
			}
			if (matrice[i][j] == ' ')
				distR[i][j] = distJ[i][j] = 2000000000;//INT_MAX;
		}
	}
}

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

//calculeaza dist pt Rom
void BFS_R() {
	list <punct> queue;
	queue.push_back(rom);

	while (!queue.empty()) {
		punct curent = queue.front();
		queue.pop_front();

		int k;
		for (k = 1; k <= 9; k++) {
			//se updateaza distanta curenta daca e cazul si in caz afirmativ acesta e trecut in coada
			if (distR[curent.i + iDirectie[k]][curent.j] + jDirectie[k])
				if (distR[curent.i + iDirectie[k]][curent.j + jDirectie[k]] > distR[curent.i][curent.j] + 1) {
					distR[curent.i + iDirectie[k]][curent.j + jDirectie[k]] = distR[curent.i][curent.j] + 1;
					punct nou; nou.i = curent.i + iDirectie[k]; nou.j = curent.j + jDirectie[k];
					queue.push_back(nou);
				}
		}
	}
}

//calculeaza dist pt Jul
void BFS_J() {
	list <punct> queue;
	queue.push_back(jul);

	while (!queue.empty()) {
		punct curent = queue.front();
		queue.pop_front();

		int k;
		for (k = 1; k <= 9; k++) {
			//se updateaza distanta curenta daca e cazul si in caz afirmativ acesta e trecut in coada
			if (distR[curent.i + iDirectie[k]][curent.j] + jDirectie[k])
				if (distJ[curent.i + iDirectie[k]][curent.j + jDirectie[k]] > distJ[curent.i][curent.j] + 1) {
					distJ[curent.i + iDirectie[k]][curent.j + jDirectie[k]] = distJ[curent.i][curent.j] + 1;
					punct nou; nou.i = curent.i + iDirectie[k]; nou.j = curent.j + jDirectie[k];
					queue.push_back(nou);
				}
		}
	}
}

//cauta punctul de intalnire
void pctIntalnire() {
	int tmin = INT_MAX, x=0, y=0;
	int i, j;
	for (i=1; i<=n; i++)
		for (j = 1; j <= m; j++) {
			if (distR[i][j])
				if (distR[i][j] == distJ[i][j])
					if (distR[i][j] < tmin) {
						tmin = distR[i][j];
						x = i;
						y = j;
					}
		}
	out << tmin+1 << " " << x << " " << y;
}

int main()
{
	citire();
	BFS_R();
	BFS_J();
	pctIntalnire();
    return 0;
}