Cod sursa(job #2423322)

Utilizator irares27Rares Munteanu irares27 Data 21 mai 2019 01:05:02
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <vector>
#include <iostream>
#include <fstream>
#include<queue>
using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");


int verif_coord(int i, int j, int n, int m)
{
	if (i > n || i < 1)return 0;
	if (j > m || j < 1)return 0;
	return 1;
}
struct punct
{
	int i, j;
};

void BFS(vector<vector<int>>&matrix, punct start)
{
	int n = matrix.size(); n--;
	int m = matrix[0].size(); m--;
	int offseti[8] = { 0,1,1,1,0,-1,-1,-1 }, offsetj[8] = { -1,-1,0,1,1,1,0,-1 };
	punct aux;
	queue<punct> myQueue;
	myQueue.push(start);
	while (!myQueue.empty())
	{
		aux = myQueue.front();
		myQueue.pop();
		for (int i = 0; i < 8; i++)
		{
			punct nou;
			nou.i = aux.i + offseti[i];
			nou.j = aux.j + offsetj[i];
			if (verif_coord(nou.i,nou.j,n,m) && matrix[nou.i][nou.j] == 0)
			{
				matrix[nou.i][nou.j] = matrix[aux.i][aux.j] + 1;
				myQueue.push(nou);
			}
		}
	}
}

int main()
{
	int n, m;
	f >> n >> m;
	punct R, J;
	vector<vector<char>>matrix(n + 1, vector<char>(m + 1));
	vector<vector<int>>Rm(n + 1, vector<int>(m + 1));
	vector<vector<int>>Jm(n + 1, vector<int>(m + 1));

	f.get();
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{		
			f.get(matrix[i][j]);
			if (matrix[i][j] == 'R')
			{
				R.i = i;
				R.j = j;
				Rm[i][j] = 1;
				Jm[i][j] = 0;
			}
			else
				if (matrix[i][j] == 'J')
				{
					J.i = i;
					J.j = j;
					Jm[i][j] = 1;
					Rm[i][j] = 0;
				}
				else
				{
					if (matrix[i][j] == 'X')
						Rm[i][j] = Jm[i][j] = -1;
					else
						Rm[i][j] = Jm[i][j] = 0;
				}
		}
	
		f.get();
	}
	BFS(Rm, R);
	BFS(Jm, J);

	punct fin;
	int min = INT32_MAX;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (Rm[i][j] == Jm[i][j] and Rm[i][j] > 0 and Rm[i][j] < min)
			{
				min = Rm[i][j];
				fin.i = i;
				fin.j = j;
			}
		}
	g << min <<" "<< fin.i << " " << fin.j;

	return 0;
}