Cod sursa(job #2526192)

Utilizator sebimihMihalache Sebastian sebimih Data 18 ianuarie 2020 12:22:36
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.38 kb

#include <iostream>
#include <fstream>
#include <string>
#include <limits.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 105;
const int Inf = INT_MAX;

ifstream fin("rj.in");
ofstream fout("rj.out");

#define X first
#define Y second

typedef pair<int, int> coordonate;
typedef pair<coordonate, int> TXY;

bool InMatrice(coordonate p, int n, int m)
{
	return p.X >= 1 && p.X <= n && p.Y >= 1 && p.Y <= m;
}

void FillMatrice(int Harta[N][N], coordonate Start, int n, int m)
{
	queue<coordonate> lista;
	lista.push(Start);

	while (!lista.empty())
	{
		// Luam punctul la care suntem
		coordonate p = lista.front();
		lista.pop();

		// Verificam fiecare vecin
		coordonate neighbour;

		int DirX[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
		int DirY[] = { 1, -1, 0, 0, 1, -1, 1, -1 };

		for (int i = 0; i < 8; i++)
		{
			neighbour.X = p.X + DirX[i];
			neighbour.Y = p.Y + DirY[i];

			if (InMatrice(neighbour, n, m)
				&& Harta[neighbour.X][neighbour.Y] == Inf
				)
			{
				lista.push(neighbour);
				Harta[neighbour.X][neighbour.Y] = Harta[p.X][p.Y] + 1;
			}
		}
	}
}

TXY ComparareMatrice(int HartaRomeo[N][N], int HartaJulieta[N][N], int n, int m)
{
	coordonate punctIntalnire;
	int NrPasiMin = INT_MAX;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (HartaRomeo[i][j] == HartaJulieta[i][j]
				&& HartaRomeo[i][j] > 0
				&& HartaRomeo[i][j] < NrPasiMin)
			{
				NrPasiMin = HartaRomeo[i][j];
				punctIntalnire = { i, j };
			}
		}
	}

	return { punctIntalnire, NrPasiMin };
}

int main()
{
	int n, m;
	fin >> n >> m;
	int HartaRomeo[N][N];
	coordonate LocRomeo;
	int HartaJulieta[N][N];
	coordonate LocJulieta;

	string Matrice;
	getline(fin, Matrice);  // Luam prima linia si o ignoram

	for (int i = 1; i <= n; i++)  // Linie
	{
		getline(fin, Matrice);

		int j = 1;
		for (char c : Matrice)
		{
			if (c == ' ')
			{
				HartaRomeo[i][j] = Inf;
				HartaJulieta[i][j] = Inf;
			}
			else if (c == 'R')
			{
				LocRomeo = { i, j };
				HartaRomeo[i][j] = 1;
				HartaJulieta[i][j] = -1;
			}
			else if (c == 'J')
			{
				LocJulieta = { i, j };
				HartaRomeo[i][j] = -1;
				HartaJulieta[i][j] = 1;
			}
			else // c == 'X'
			{
				HartaRomeo[i][j] = -1;
				HartaJulieta[i][j] = -1;
			}

			j++;
		}
	}

	// Umple matricele
	FillMatrice(HartaRomeo, LocRomeo, n, m);
	FillMatrice(HartaJulieta, LocJulieta, n, m);

	// Compara matricele
	TXY TimpLoc = ComparareMatrice(HartaRomeo, HartaJulieta, n, m);
	int Timp = TimpLoc.second;
	coordonate Loc = TimpLoc.first;

	fout << Timp << ' ' << Loc.first << ' ' << Loc.second;
}


#include <iostream>
#include <fstream>
#include <string>
#include <limits.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 105;
const int Inf = INT_MAX;

ifstream fin("rj.in");
ofstream fout("rj.out");

#define X first
#define Y second

typedef pair<int, int> coordonate;
typedef pair<coordonate, int> TXY;

bool InMatrice(coordonate p, int n, int m)
{
	return p.X >= 1 && p.X <= n && p.Y >= 1 && p.Y <= m;
}

void FillMatrice(int Harta[N][N], coordonate Start, int n, int m)
{
	queue<coordonate> lista;
	lista.push(Start);

	while (!lista.empty())
	{
		// Luam punctul la care suntem
		coordonate p = lista.front();
		lista.pop();

		// Verificam fiecare vecin
		coordonate neighbour;

		int DirX[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
		int DirY[] = { 1, -1, 0, 0, 1, -1, 1, -1 };

		for (int i = 0; i < 8; i++)
		{
			neighbour.X = p.X + DirX[i];
			neighbour.Y = p.Y + DirY[i];

			if (InMatrice(neighbour, n, m)
				&& Harta[neighbour.X][neighbour.Y] == Inf
				)
			{
				lista.push(neighbour);
				Harta[neighbour.X][neighbour.Y] = Harta[p.X][p.Y] + 1;
			}
		}
	}
}

TXY ComparareMatrice(int HartaRomeo[N][N], int HartaJulieta[N][N], int n, int m)
{
	coordonate punctIntalnire;
	int NrPasiMin = INT_MAX;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (HartaRomeo[i][j] == HartaJulieta[i][j]
				&& HartaRomeo[i][j] > 0
				&& HartaRomeo[i][j] < NrPasiMin)
			{
				NrPasiMin = HartaRomeo[i][j];
				punctIntalnire = { i, j };
			}
		}
	}

	return { punctIntalnire, NrPasiMin };
}

int main()
{
	int n, m;
	fin >> n >> m;
	int HartaRomeo[N][N];
	coordonate LocRomeo;
	int HartaJulieta[N][N];
	coordonate LocJulieta;

	string Matrice;
	getline(fin, Matrice);  // Luam prima linia si o ignoram

	for (int i = 1; i <= n; i++)  // Linie
	{
		getline(fin, Matrice);

		int j = 1;
		for (char c : Matrice)
		{
			if (c == ' ')
			{
				HartaRomeo[i][j] = Inf;
				HartaJulieta[i][j] = Inf;
			}
			else if (c == 'R')
			{
				LocRomeo = { i, j };
				HartaRomeo[i][j] = 1;
				HartaJulieta[i][j] = -1;
			}
			else if (c == 'J')
			{
				LocJulieta = { i, j };
				HartaRomeo[i][j] = -1;
				HartaJulieta[i][j] = 1;
			}
			else // c == 'X'
			{
				HartaRomeo[i][j] = -1;
				HartaJulieta[i][j] = -1;
			}

			j++;
		}
	}

	// Umple matricele
	FillMatrice(HartaRomeo, LocRomeo, n, m);
	FillMatrice(HartaJulieta, LocJulieta, n, m);

	// Compara matricele
	TXY TimpLoc = ComparareMatrice(HartaRomeo, HartaJulieta, n, m);
	int Timp = TimpLoc.second;
	coordonate Loc = TimpLoc.first;

	fout << Timp << ' ' << Loc.first << ' ' << Loc.second;
}