Cod sursa(job #2419969)

Utilizator Marius2902Chitac Marius Marius2902 Data 9 mai 2019 22:53:56
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <iostream>
#include <fstream>
#include <cstdint>
#include <queue>
using namespace std;

struct punct {
	int x, y;
};

void contur(char **M, int n, int m)
{
	int i;
	for (i = 0; i <= m + 1; i++)
		M[0][i] = M[n + 1][i] = 'X';
	for (i = 0; i <= n + 1; i++)
		M[i][0] = M[i][m + 1] = 'X';
}

void BFS(char **M, punct start)
{
	int offsetx[8] = { 0,1,1,1,0,-1,-1,-1 }, offsety[8] = { -1,-1,0,1,1,1,0,-1 };
	punct aux;
	queue<punct> Q;
	Q.push(start);
	while (!Q.empty())
	{
		aux = Q.front();
		Q.pop();
		for (int i = 0; i < 8; i++)
		{
			int inou = aux.y + offsety[i], jnou = aux.x + offsetx[i];
			punct aux2 = { jnou,inou };
			if (M[inou][jnou] == ' ')
			{
				M[inou][jnou] = M[aux.y][aux.x] + 1;
				Q.push(aux2);
			}
		}
	}
}

int main()
{
	ifstream in("rj.in");
	ofstream out("rj.out");
	int n, m, i, j;
	punct R, J;
	in >> n >> m;
	char **M = new char*[n + 2], **Jm = new char*[n + 2], **Rm = new char*[n + 2];
	for (i = 0; i <= n + 1; i++)
	{
		M[i] = new char[m + 2];
		Rm[i] = new char[m + 2];
		Jm[i] = new char[m + 2];
	}
	in.get();
	for (i = 1; i <= n; i++)
		in.getline(M[i] + 1, m + 1);
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			if (M[i][j] == 'R')
			{
				R.x = j;
				R.y = i;
				M[i][j] = ' ';
			}
			else if (M[i][j] == 'J')
			{
				J.x = j;
				J.y = i;
				M[i][j] = ' ';
			}
			Rm[i][j] = Jm[i][j] = M[i][j];

		}
	}
	Rm[R.y][R.x]++;
	Jm[J.y][J.x]++;
	contur(M, n, m);
	contur(Rm, n, m);
	contur(Jm, n, m);
	BFS(Rm, R);
	BFS(Jm, J);
	Rm[R.y][R.x] = 'X';
	Jm[J.y][J.x] = 'X';
	punct poz = { INT32_MAX,INT32_MAX };
	int minn = INT32_MAX;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			if (Rm[i][j] != ' ' and Rm[i][j] != 'X' and Rm[i][j] == Jm[i][j] and (Rm[i][j] - ' ' < minn or (Rm[i][j] - ' ' == minn and (i < poz.y or (i == poz.y and j < poz.x)))))
			{
				minn = Rm[i][j] - ' ';
				poz.x = j;
				poz.y = i;
			}
	out << minn << " " << poz.y << " " << poz.x;
	return 0;
}