Cod sursa(job #244672)

Utilizator mist000000 mist Data 15 ianuarie 2009 19:29:50
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <list>

using namespace std;

int m, n, rl, rc, jl, jc;
char *terrain;
int *romeoMap, *julietMap;

inline char& cell(char *map, int line, int col)
{
	return map[line * n + col];
}

inline int& cell(int *map, int line, int col)
{
	return map[line * n + col];
}

void readInput()
{
	FILE *in = fopen("rj.in", "r");
	fscanf(in, "%d %d\n", &m, &n);

	terrain = new char[m * n];
	romeoMap = new int[m * n];
	memset(romeoMap, 0, m * n * sizeof(*romeoMap));
	julietMap = new int[m * n];
	memset(julietMap, 0, m * n * sizeof(*julietMap));

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cell(terrain, i, j) = fgetc(in);
			if (cell(terrain, i, j) == 'R') {
				rl = i;
				rc = j;
				cout << "romeo found" << endl;
			} else if (cell(terrain, i, j) == 'J') {
				jl = i;
				jc = j;
				cout << "Juliet found" << endl;
			}
		}
		if (i < m - 1) {
			// read '\n'
			while(fgetc(in) != '\n')
				;
		}
	}
	fclose(in);
}

void computeTimes(int *map, int startl, int startc)
{
	// N, NW, W, SW, S, SE, E, NE
	static const int dl[] = {-1, -1, 0, 1, 1, 1, 0, -1};
	static const int dc[] = {0, -1, -1, -1, 0, 1, 1, 1};
	list<int> lst;
	lst.push_back(startl);
	lst.push_back(startc);

	while (!lst.empty()) {
		int l = lst.front();
		lst.pop_front();
		int c = lst.front();
		lst.pop_front();
		int crtDist = cell(map, l, c);

		for (unsigned int i = 0; i < sizeof(dl) / sizeof(*dl); i++) {
			int l2 = l + dl[i];
			int c2 = c + dc[i];
			if (l2 >= 0 && l2 < m && c2 >= 0 && c2 < n &&
					cell(terrain, l2, c2) == ' ' &&
					(cell(map, l2, c2) == 0 ||
					 cell(map, l2, c2) > crtDist + 1)) {
				cell(map, l2, c2) = crtDist + 1;
				lst.push_back(l2);
				lst.push_back(c2);
			}
		}
	}
}

int main()
{
	readInput();
	computeTimes(romeoMap, rl, rc);
	computeTimes(julietMap, jl, jc);

	bool found = false;
	int solCount, solL, solC;
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++) {
			if (cell(romeoMap, i, j) == cell(julietMap, i, j) &&
					cell(romeoMap, i, j) != 0) {
				if (!found || cell(romeoMap, i, j) < solCount) {
					solCount = cell(romeoMap, i, j);
					solL = i;
					solC = j;
				}
				found = true;
			}
		}

	ofstream out("rj.out");
	if (!found)
		out << "0 0 0";
	else
		out << solCount + 1 << ' ' << solL + 1 << ' ' << solC + 1;
	out.close();

	return 0;
}