Cod sursa(job #1996320)

Utilizator trifangrobertRobert Trifan trifangrobert Data 30 iunie 2017 23:56:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.08 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())
	{
		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] << " ";
			cout << "\n";
		}
	if(x==2)
		for (int i = 1;i <= n;i++)
			{
				for (int j = 1;j <= m;j++)
					cout << b[i][j] << " ";
				cout << "\n";
			}
	if (x == 3)
		for (int i = 1;i <= n;i++)
		{
			for (int j = 1;j <= m;j++)
				cout << c[i][j] << " ";
			cout << "\n";
		}
	cout << "\n";
}
*/

void Solution()
{
	bool ok = true;
	for (int i = 1;i <= n;i++)
	{
		if (ok)
			for (int j = 1;j <= m;j++)
			{
				if (b[i][j] != infinite && c[i][j] != infinite)
				{
					if (b[i][j] == c[i][j] && ok)
					{
						ok = false;
						g << b[i][j] + 1 << " " << i << " " << j << "\n";
						break;
					}
					else
					{
						int dx[] = { 0,0,1,-1,-1,-1,1,1 };
						int dy[] = { 1,-1,0,0,-1,1,-1,1 };
						for (int k = 0;k < 8;k++)
						{
							int x, y;
							x = i + dx[k];
							y = j + dy[k];
							if (b[i][j] == c[x][y] && x != 0 && y != 0)
							{
								ok = false;
								g << b[i][j] + 1 + 1<< " ";// al doilea +1 e de la faptul ca am plecat cu Lee-ul de la 0
								if (j < y)
									g << i << " " << j << "\n";
								else
									g << i << " " << y << "\n";
								break;
							}
						}
					}
				}
			}
		else
			break;
	}
}

int main()
{
	f >> n >> m;
	f.get();
	for (int i = 1;i <= n;i++)
	{
		f.getline(s, dimension);
		for (int j = 0;s[j];j++)
		{
			b[i][j+1] = infinite;
			c[i][j + 1] = infinite;
			if (s[j] == ' ')
				a[i][j+1] = false;
			if (s[j] == 'X')
				a[i][j+1] = true;
			if (s[j] == 'R')
			{
				xr = i;
				yr = j + 1;
				a[i][j+1] = false;
				b[i][j+1] = 0;
			}
			if (s[j] == 'J')
			{
				xj = i;
				yj = j + 1;
				a[i][j+1] = false;
				c[i][j+1] = 0;
			}
		}
	}
	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();
	//_getch();
	return 0;
}