Cod sursa(job #2781783)

Utilizator vladalex420@gmail.comLuta Vlad Alexandru [email protected] Data 10 octombrie 2021 14:21:59
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

int h; int w;

struct Point
{
	int x = 0;
	int y = 0;
	int getIndex() { return x + y * h; }
	void setFromIndex(int i) { x = i % w; y = i / h; }
};

int main()
{

	std::ifstream in("rj.in");
	in >> h >> w;
	char notUsed=0;
	in.read(&notUsed, 1);

	char mat[100][100];

	Point romeo;
	Point juliet;

	for (int y = 0; y < h; y++)
	{
		char line[101] = {};
		in.read(line, w + 1);
		for (int x = 0; x < w; x++)
		{
			mat[y][x] = line[x];
			if (line[x] == 'R')
			{
				romeo = {x,y};
			}
			else if (line[x] == 'J')
			{
				juliet = {x,y};
			}
		}
	}
	in.close();

	std::vector<char> visited;
	visited.resize(w * h);
	
	std::vector<int> returnPath; //this will trace any node back to "from" using the shortest path
	returnPath.resize(w*h, -1);

	auto romeoIndex = romeo.getIndex();
	auto julietIndex = juliet.getIndex();

	visited[romeoIndex] = 1;

	std::queue<Point> nodesToVisit; //current node
	nodesToVisit.emplace(romeo);
	bool found = 0;
	while (!nodesToVisit.empty() && !found)
	{
		auto point = nodesToVisit.front();
		nodesToVisit.pop();
		std::vector<Point> vecini;
		vecini.reserve(8);

		if (point.x > 0 && point.y > 0) { vecini.push_back({point.x - 1, point.y - 1}); }
		if (point.y > 0) { vecini.push_back({point.x, point.y - 1}); }
		if (point.x < w - 1 && point.y > 0) { vecini.push_back({point.x + 1, point.y - 1}); }

		if (point.x > 0) { vecini.push_back({point.x - 1, point.y}); }
		if (point.x > 0 && point.y < h - 1) { vecini.push_back({point.x - 1, point.y + 1}); }

		if (point.x < w - 1) { vecini.push_back({point.x + 1, point.y}); }
		if (point.y < h - 1) { vecini.push_back({point.x, point.y + 1}); }
		if (point.x < w - 1 && point.y < h - 1) { vecini.push_back({point.x + 1, point.y + 1}); }

		for (auto i = 0; i < vecini.size(); i++)
		{
			int index = vecini[i].getIndex();

			if (visited[index] == 0 && mat[vecini[i].y][vecini[i].x] != 'X')
			{
				visited[index] = 1;
				nodesToVisit.push(vecini[i]);
				returnPath[index] = point.getIndex();
			
				if (
					vecini[i].x == juliet.x &&
					vecini[i].y == juliet.y
					)
				{
					found = true;
					break;
				}
			}

		}
	}


	std::vector<int> returnVector;
	returnVector.reserve(200);
	{
		int el = returnPath[julietIndex];
		returnVector.push_back(julietIndex);
		while (el >= 0)
		{
			returnVector.push_back(el);
			el = returnPath[el];
		}
	}

	//for (auto i : returnVector)
	//{
	//	Point p;
	//	p.setFromIndex(i);
	//	std::cout << p.x << " " << p.y << "\n";
	//}


	std::ofstream out("rj.out");

	int s = returnVector.size() / 2;
	bool odd = returnVector.size() % 2;
	Point p;
	p.setFromIndex(returnVector[s]);


	out << s + 1 << " ";
	out << p.y + 1 << " " << p.x + 1;

	out.close();

	//std::cin.get();

	return 0;
}