Cod sursa(job #1148513)

Utilizator rucarRucareanu Alexandru rucar Data 20 martie 2014 20:44:44
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <fstream>
#include <queue>
#include <limits>
using namespace std;

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

struct per{
	int l, c;
};

void det_drum(int **, int, int, int, int);
int bun(per, int, int);

int main()
{
	int n, m, ri, rj, ji, jj;
	f >> n >> m;
	int **a = new int*[n + 1];
	for (int i{ 1 }; i <= n; i++)
		a[i] = new int[m + 1];
	int **b = new int*[n + 1];
	for (int i{ 1 }; i <= n; i++)
		b[i] = new int[m + 1];
	for (int i{ 1 }; i <= n; i++)
	{
		for (int j{ 1 }; j <= m; j++)
		{
			a[i][j] = 0; b[i][j] = 0;
		}
	}
	char c;
	for (int i{ 1 }; i <= n; i++)
	{
		for (int j{ 1 }; j <= m; j++)
		{
			f.get(c);
			if (c == '\n') f.get(c);
			if (c == 'X') a[i][j] = b[i][j] = -1;
			if (c == 'R'){ri = i;  rj = j;}
			if (c == 'J'){ ji = i; jj = j;}
		}
	}
	det_drum(a, n, m, ri, rj);
	det_drum(b, n, m, ji, jj);
	int timp = 1000000, i_int = 0, j_int = 0;
	for (int i{ 1 }; i <= n; i++)
	{
		for (int j{ 1 }; j <= m; j++)
		{
			if (a[i][j] > 1 && a[i][j] == b[i][j] && timp > a[i][j])
			{
				timp = a[i][j];
				i_int = i;
				j_int = j;
			}
		}
	}
	g << timp << " " << i_int << " " << j_int;
	return 0;
}

void det_drum(int **a, int n, int m, int x, int y)
{
	int pozl[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
	int pozc[] = { 1, 1, 0, -1, -1, -1, 0, 1 };
	queue <per> q;
	per aux{ x, y };
	q.push(aux);
	a[x][y] = 1;
	while (!q.empty())
	{
		per coor = q.front();
		q.pop();
		for (int k{ 0 }; k < 8; k++)
		{
			per coor_noi{ coor.l + pozl[k], coor.c + pozc[k] };
			if (bun(coor_noi, n, m) && !a[coor_noi.l][coor_noi.c])
			{
				a[coor_noi.l][coor_noi.c] = a[coor.l][coor.c] + 1;
				q.push(coor_noi);
			}
		}
	}
}

int bun(per coor, int n, int m)
{
	if (coor.l >= 1 && coor.l <= n && coor.c >= 1 && coor.c <= m)
		return 1;
	return 0;
}