Cod sursa(job #2418145)

Utilizator Marius2902Chitac Marius Marius2902 Data 3 mai 2019 20:14:11
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

struct punct {
	int x, y, timp;
};


bool notcommon(deque<punct> R, deque<punct> J, punct& maxim)
{	
	bool r = true;
	deque<punct> ::iterator it1, it2;;
	for (it1 = R.begin(); it1 != R.end(); it1++)
		for (it2 = J.begin(); it2 != J.end(); it2++)
			if (it1->x == it2->x and it1->y == it2->y and it1->timp==it2->timp)
			{
				r = false;
				if (it1->y < maxim.y)
					maxim = *it1;
				else
					if (it1->x < maxim.x and it1->y == maxim.y)
						maxim = *it1;
			}
	return r;
}

bool inside(int i, int j, int n, int m)
{
	if (i < 0 or i >= n or j < 0 or j >= m)
		return false;
	return true;
}

void afisare(int **M, int n, int m)
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
			cout << M[i][j] << " ";
		cout << '\n';
	}
	cout << "******************************\n";
}

int main()
{	
	ifstream in("rj.in");
	ofstream out("rj.out");
	int n, m, i, j, offsetx[8] = { 0,1,1,1,0,-1,-1,-1 }, offsety[8] = {-1,-1,0,1,1,1,0,-1},tmin=2;
	char c;
	in >> n >> m;
	punct R, J;
	deque<punct> RQ,JQ,Meeting;
	punct a, b;
	int **M = new int*[n];
	for (i = 0; i < n; i++)
		M[i] = new int[m];
	in >> noskipws >> c;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			in >> noskipws >> c;
			if (c == 'R')
			{	
				M[i][j] = -1;
				R.x = j;
				R.y = i;
			}
			else {
				if (c == 'J')
				{
					M[i][j] = -1;
					J.x = j;
					J.y = i;
				}
				else
				{
					if (c == 'X')
						M[i][j] = -1;
					else
						M[i][j] = 0;
				}
			}
		}
		in>>noskipws>>c;
	}
	punct maxim = { n,m };
	R.timp = J.timp = 1;
	RQ.push_back(R);
	JQ.push_back(J);
	while (notcommon(RQ,JQ,maxim))
	{	
		a = RQ[0];
		b = JQ[0];
		RQ.pop_front();
		JQ.pop_front();
		for (i = 0; i < 8; i++)
		{
			int inou, jnou,tnou;
			inou = a.y + offsety[i];
			jnou = a.x + offsetx[i];
			if (inside(inou, jnou, n, m) and M[inou][jnou]!=-1)
			{	
				M[inou][jnou] = 0;
				tnou = a.timp + 1;
				punct aux = { jnou,inou,tnou };
				RQ.push_back(aux);
			}
		}
		for (i = 0; i < 8; i++)
		{
			int inou, jnou,tnou;
			inou = b.y + offsety[i];
			jnou = b.x + offsetx[i];
			if (inside(inou, jnou, n, m) and M[inou][jnou] != -1)
			{
				M[inou][jnou] = 0;
				tnou = b.timp + 1;
				punct aux = { jnou,inou,tnou };
				JQ.push_back(aux);
			}
		}
		tmin++;
	}
	out << maxim.timp <<" "<< maxim.y + 1 << " " << maxim.x + 1;
	return 0;
}