Cod sursa(job #2418924)

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

struct punct {
	int x, y;
};

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];
}

bool isnotvisited(vector<punct> V, punct a)
{
	for (int i = 0; i < V.size(); i++)
		if (V[i].x == a.x and V[i].y == a.y)
			return false;
	return true;
}

void find_eo(int x, int y, punct J, int offsetx[], int offsety[], int **M, int n, int m, vector<punct> &max_p)
{
	queue<vector<punct>> q;
	vector<punct> path;
	punct aux = { x,y };
	path.push_back(aux);
	q.push(path);
	while(!q.empty())
	{
		path = q.front();
		q.pop();
		punct last = path[path.size() - 1];
		if (last.x == J.x and last.y == J.y and path.size()%2)
		{	
			if (max_p.size() == 0)
				max_p = path;
			else
			{
				if (path.size() == max_p.size() and (path[path.size() / 2].y < max_p[max_p.size() / 2].y or (path[path.size() / 2].y == max_p[max_p.size() / 2].y and path[path.size() / 2].x < max_p[max_p.size() / 2].x)))
					max_p = path;
				else
				{
					while (!q.empty())
						q.pop();
				}
			}
		}
		else
			for (int i = 0; i < 8; i++)
			{
				int inou = last.y + offsety[i];
				int jnou = last.x + offsetx[i];
				punct auxiliar = { jnou,inou };
				if (inside(inou, jnou, n, m) and M[inou][jnou]==0 and isnotvisited(path, auxiliar))
				{	
					vector<punct> newpath(path);
					newpath.push_back(auxiliar);
					q.push(newpath);
				}
			}
	}
}

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] = 0;
					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)
	{	
		vector<punct> max_p;
		find_eo(R.x, R.y, J, offsetx, offsety, M, n, m, max_p);
		if (max_p.size())
			out << max_p.size() / 2 + 1 << " " << max_p[max_p.size() / 2].y + 1 << " " << max_p[max_p.size() / 2].x + 1;
		else
			out << "Nu a ajuns";
	}
	else
		out << 1 << " " << J.y << " " << J.x;
	return 0;
}