Cod sursa(job #1996330)

Utilizator trifangrobertRobert Trifan trifangrobert Data 1 iulie 2017 01:12:26
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <fstream>
#include <queue>
#include <algorithm>

#define INFINITE 2000000
#define DIMENSION 110

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");
int n, m;
queue < pair <int, int> > st;
bool a[DIMENSION][DIMENSION];
int b[DIMENSION][DIMENSION];
int c[DIMENSION][DIMENSION];
char s[DIMENSION];
int xr, yr, xj, yj;

void Bord_Matrix()
{
	for (int i = 0;i <= n + 1;i++)
		a[i][0] = a[i][m + 1] = true;
	for (int i = 0;i <= m + 1;i++)
		a[0][i] = a[n + 1][i] = true;
}

void Lee(int matrix[][DIMENSION],int X,int Y)
{
	int i, j, x, y;
	int dx[] = {0,0,1,-1,-1,-1,1,1};
	int dy[] = {1,-1,0,0,-1,1,-1,1};
	st.push(make_pair(X, Y));
	while (!st.empty())
	{
		/*pair<int, int> aux = st.front();
		i = aux.first;
		j = aux.second;*/
		i = st.front().first;
		j = st.front().second;
		st.pop();
		for (int k = 0;k < 8;k++)
			{
				x = i + dx[k];
				y = j + dy[k];
				if (a[x][y] == false && matrix[x][y] > matrix[i][j] + 1)
				{
					matrix[x][y] = matrix[i][j] + 1;
					st.push(make_pair(x, y));
				}
			}
	}
}

/*
void Display_Matrix(int x)
{
	if(x==1)
	for (int i = 1;i <= n;i++)
		{
			for (int j = 1;j <= m;j++)
				cout << a[i][j] << "\t";
			cout << "\n";
		}
	if(x==2)
		for (int i = 1;i <= n;i++)
			{
				for (int j = 1;j <= m;j++)
					cout << b[i][j] << "\t";
				cout << "\n";
			}
	if (x == 3)
		for (int i = 1;i <= n;i++)
		{
			for (int j = 1;j <= m;j++)
				cout << c[i][j] << "\t";
			cout << "\n";
		}
	cout << "\n";
}
*/

void Solution()
{
	int minim = INFINITE;
	pair<int, int> poz;
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if ((b[i][j] != INFINITE && c[i][j] != INFINITE) && b[i][j] < minim && b[i][j] == c[i][j])
			{
				minim = b[i][j];
				poz.first = i;
				poz.second = j;
			}
		}
	}
	g << minim << " " << poz.first << " " << poz.second << "\n";
}

int main()
{
	f >> n >> m;
	f.get();
	for (int i = 1;i <= n;i++)
	{
		f.getline(s+1, DIMENSION);
		for (int j = 1;j<=m;j++)
		{
			b[i][j] = INFINITE;
			c[i][j] = INFINITE;
			if (s[j] == ' ')
				a[i][j] = false;
			if (s[j] == 'X')
				a[i][j] = true;
			if (s[j] == 'R')
			{
				xr = i;
				yr = j;
				a[i][j] = false;
				b[i][j] = 1;
			}
			if (s[j] == 'J')
			{
				xj = i;
				yj = j;
				a[i][j] = false;
				c[i][j] = 1;
			}
		}
	}
	Bord_Matrix();
	Lee(b,xr,yr);
	Lee(c,xj,yj);
	//Display_Matrix(1);
	//Display_Matrix(2);
	//Display_Matrix(3);
	Solution();
	// de facut doua lee uri
	// de tinut cont de cazul special cand nu se intalnesc pe aceeasi pozitie
	f.close();
	g.close();
	return 0;
}