Cod sursa(job #1147652)

Utilizator TwoOfDiamondsDaniel Alexandru Radu TwoOfDiamonds Data 20 martie 2014 00:20:12
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <queue>
#include <string>
#include <fstream>
#include <iostream>

using namespace std;

struct nod
{
	int x, y;
} *romeo, *julieta;

struct val
{
	int x, y, cost;
};

int matRom[100][100], matJul[100][100];
bool matViz[100][100];
int linii, coloane;
queue<nod*> coada;

bool isOk(int x, int y)
{
	if (x >= 0 && x < linii && y >= 0 && y < coloane && matViz[x][y] == false)
		return true;
	return false;
}

void flood(int x, int y, int mat[100][100], int cost)
{
	if(isOk(x, y) && mat[x][y] != -1)
		{
			nod *n = new nod;
			n->x = x;
			n->y = y;
			coada.push(n);
			if(mat[x][y] == 0 || mat[x][y] > cost)
				mat[x][y] = cost;
			matViz[x][y] = true;
		}
}

int main()
{
	ifstream IN("rj.in");
	string str;
	romeo = new nod;
	julieta = new nod;

	IN >> linii >> coloane;

	getline(IN, str);

	for (int i = 0 ; i < linii ; i++)
	{
		getline(IN, str);
		for (int j = 0; j < coloane; j++)
		{
			matRom[i][j] = 0;
			matJul[i][j] = 0;

			if(str[j] == 'R')
			{
				romeo->x = i;
				romeo->y = j;
			}
			else if (str[j] == 'J')
			{
				julieta->x = i;
				julieta->y = j;
			}

			if(str[j] == 'X')
			{
				matRom[i][j] = -1;
				matJul[i][j] = -1;
			}
		}
	}

	IN.close();

	for (int i = 0 ; i < linii; i++)
		for (int j = 0 ; j < coloane; j++)
			matViz[i][j] = false;
	matViz[romeo->x][romeo->y] = true;

	coada.push(romeo);

	//cout <<"romeo: " << endl;
	while(!coada.empty())
	{
		nod *curr = coada.front();
		//cout << "cost: " << matRom[curr->x][curr->y] << " x: " <<curr->x << " y: " << curr->y << endl;
		coada.pop();
		int x = curr->x, y = curr->y;
		int cost = matRom[x][y] + 1;

		flood(x - 1, y - 1, matRom, cost);
		flood(x - 1, y    , matRom, cost);
		flood(x - 1, y + 1, matRom, cost);
		flood(x,     y - 1, matRom, cost);
		flood(x,     y + 1, matRom, cost);
		flood(x + 1, y - 1, matRom, cost);
		flood(x + 1, y    , matRom, cost);
		flood(x + 1, y + 1, matRom, cost);

		delete curr;
	}
	for (int i = 0 ; i < linii; i++)
		for (int j = 0 ; j < coloane; j++)
			matViz[i][j] = false;
	matViz[julieta->x][julieta->y] = true;

	coada.push(julieta);

	//cout << "julieta: " << endl;
	while(!coada.empty())
	{
		nod *curr = coada.front();
		//cout << "cost: " << matJul[curr->x][curr->y] << " x: " <<curr->x << " y: " << curr->y << endl;
		int x = curr->x, y = curr->y;
		coada.pop();
		int cost = matJul[x][y] + 1;

		flood(x - 1, y - 1, matJul, cost);
		flood(x - 1, y    , matJul, cost);
		flood(x - 1, y + 1, matJul, cost);
		flood(x, y - 1    , matJul, cost);
		flood(x, y + 1    , matJul, cost);
		flood(x + 1, y - 1, matJul, cost);
		flood(x + 1, y    , matJul, cost);
		flood(x + 1, y + 1, matJul, cost);

		delete curr;
	}

	ofstream OUT ("rj.out");

	val v;
	v.x = 0; v.y = 0;
	v.cost = 999999;

	for (int i = 0 ; i < linii; i++)
	{
		for (int j = 0 ; j < coloane; j++)
		{
			if(matRom[i][j] == matJul[i][j] && matRom[i][j] != -1 && matRom[i][j] != 0 && (romeo->x != i || romeo->y != j) && (julieta->x != i || julieta->y != j))
			{
				if(matRom[i][j] < v.cost)
				{
					v.cost = matRom[i][j];
					v.x = i;
					v.y = j;
				}
			}
		}
	}

	OUT << v.cost << " " << v.x << " " << v.y << "\n";

	return 0;
}