Cod sursa(job #2418893)

Utilizator Marius2902Chitac Marius Marius2902 Data 6 mai 2019 18:40:08
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <iostream>
#include <fstream>
#include <cstdint>
using namespace std;

struct punct {
	int x, y;
};

struct destinatie{
	int 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 copy(punct *&min_f, punct *f, int nr)
{
	delete[] min_f;
	min_f = new punct[nr];
	for (int i = 0; i < nr; i++)
		min_f[i] = f[i];
}

void find_eo(int x, int y, punct J, int offsetx[], int offsety[], int **M,int n,int m,punct *father,int &index,int &min_index,punct* &min_f)
{	
	M[y][x] = -1;
	father[index] = { x,y };
	index++;
	int inou, jnou, i;
	for (i = 0; i < 8; i++)
	{
		inou = y + offsety[i];
		jnou = x + offsetx[i];
		if (inside(inou, jnou, n, m))
		{
			if (inou == J.y and jnou == J.x and !(index % 2) and ((index<min_index) or (index==min_index and father[index/2].y > min_f[min_index/2].y) or (index==min_index and father[index/2].y==min_f[min_index/2].y and father[index / 2].x > min_f[min_index / 2].x)))
			{
					min_index = index;
					copy(min_f, father, index);	
			}
			else
				if (M[inou][jnou] == 0)
					find_eo(jnou, inou, J, offsetx, offsety, M, n, m, father, index,min_index,min_f);
		}
	}
	M[y][x] = 0;
	index--;
}

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};
	char c;
	in >> n >> m;
	punct R, J;
	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;
	}
	if (R.x != J.x and R.y != J.y)
	{
		punct *father = new punct[n*m], *min_f = new punct[1];
		for (i = 0; i < n*m; i++)
			father[i] = { 0,0 };
		int indice = 0, min_indice = INT32_MAX;
		find_eo(R.x, R.y, J, offsetx, offsety, M, n, m, father, indice, min_indice, min_f);
		out << min_indice / 2 + 1 << " " << min_f[min_indice / 2].y + 1 << " " << min_f[min_indice / 2].x + 1;
	}
	else
		out << 1 << " " << J.y << " " << J.x;
	return 0;
}