Cod sursa(job #2197508)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 22 aprilie 2018 13:48:30
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
const short NMAX = 120;
unsigned short n, m;
queue <pair<unsigned short, unsigned short> > coada;
unsigned short x_R, x_J, y_R, y_J;
bool b[NMAX][NMAX];
unsigned short c[NMAX][NMAX];
char a[NMAX];
unsigned short sol, x_s, y_s;
struct
{
	short x, y;
}d[10];

void init()
{
	d[1].x = -1, d[1].y =  0; 
	d[2].x =  0, d[2].y =  1;
	d[3].x =  1, d[3].y =  0;
	d[4].x =  0, d[4].y = -1;
	d[5].x = -1, d[5].y = -1; 
	d[6].x = -1, d[6].y =  1;
	d[7].x =  1, d[7].y =  1;
	d[8].x =  1, d[8].y = -1;
}

void Citire()
{
	f >> n >> m;
	f.get();
	for(unsigned short i = 1; i <= n; i++)
	{
		f.getline(a, NMAX);
		for(unsigned short j = 0; j < strlen(a); j++)
			if(a[j] == ' ')
				b[i][j + 1] = true;
			else
			{
				b[i][j + 1] = false;
				if(a[j] == 'R')
					x_R = i, y_R = j + 1;
				else
				if(a[j] == 'J')
					x_J = i, y_J = j + 1;
			}
		if(strlen(a) < m)
			for(int j = strlen(a); j <= m; j++)
				b[i][j] = true;
	}
}

void BFS(unsigned short x, unsigned short y, unsigned short x_stop, unsigned short y_stop)
{
	init();
	c[x][y] = 1;
	coada.push(make_pair(x, y));
	bool ok = true;
	while(ok)
	{
		unsigned short x_c = coada.front().first;
		unsigned short y_c = coada.front().second;
		coada.pop();
		for(unsigned short i = 1; i <= 8; i++)
		{
			unsigned short new_X = x_c + d[i].x;
			unsigned short new_Y = y_c + d[i].y;
			if(b[new_X][new_Y] && !c[new_X][new_Y])
			{
				c[new_X][new_Y] = c[x_c][y_c] + 1;
				coada.push(make_pair(new_X, new_Y));
			}
			else
			if(new_X == x_stop && new_Y == y_stop)
			{
				ok = false;
				c[x_stop][y_stop] = c[x_c][y_c] + 1;
			}
		}
	}
	sol = (c[x_stop][y_stop] + 1) / 2;
	while(!coada.empty())
		coada.pop();
	coada.push(make_pair(x_stop, y_stop));
	ok = true;
	while(ok)
	{
		unsigned short x_c = coada.front().first;
		unsigned short y_c = coada.front().second;
		coada.pop();
		for(unsigned short i = 1; i <= 8; i++)
		{
			unsigned short new_X = x_c + d[i].x;
			unsigned short new_Y = y_c + d[i].y;
			if(c[new_X][new_Y] == c[x_c][y_c] - 1)
				coada.push(make_pair(new_X, new_Y));
			if(c[new_X][new_Y] == sol)
			{
				x_s = new_X;
				y_s = new_Y;
				ok = false;
			}
		}
	}
}

void Afisare()
{
	g << sol << " " << x_s << " " << y_s;
}

int main()
{
	Citire();
	BFS(x_R, y_R, x_J, y_J);
	Afisare();
}