Cod sursa(job #2419955)

Utilizator Marius2902Chitac Marius Marius2902 Data 9 mai 2019 22:06:03
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 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);
	punct poz = {INT32_MAX,INT32_MAX};
	int minn = INT32_MAX;
	for (i = 0; i < n; i++)
		for(j = 0; 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;
}