Cod sursa(job #2226175)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 29 iulie 2018 20:05:22
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <queue>
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

istream & in = fin;
ostream & out = fout;

struct vec2{
	typedef int type;
	type x, y;
	vec2()
	{}
	vec2(type x, type y) : x(x), y(y)
	{}
	vec2 & operator+=(const vec2 & rhs)
	{
		this->x += rhs.x;
		this->y += rhs.y;
		return *this;
	}
	vec2 & operator-=(const vec2 & rhs)
	{
		this->x -= rhs.x;
		this->y -= rhs.y;
		return *this;
	}
	vec2 operator*=(const type & rhs)
	{
		this->x *= rhs;
		this->y *= rhs;
		return *this;
	}
	vec2 operator/=(const type & rhs)
	{
		this->x /= rhs;
		this->y /= rhs;
		return *this;
	}
	bool in_bounds(vec2 vec)
	{
		return (this->x >= 1 && this->y >= 1 && this->x <= vec.x && this->y <= vec.y);
	}
};

vec2 operator-(vec2 lhs)
{
	lhs.x = -lhs.x;
	lhs.y = -lhs.y;
	return lhs;
}
vec2 operator+(vec2 lhs, const vec2 & rhs)
{
	lhs += rhs;
	return lhs;
}
vec2 operator-(vec2 lhs, const vec2 & rhs)
{
	lhs -= rhs;
	return lhs;
}
vec2 operator*(vec2 lhs, const vec2::type & rhs)
{
	lhs *= rhs;
	return lhs;
}
vec2 operator/(vec2 lhs, const vec2::type & rhs)
{
	lhs /= rhs;
	return lhs;
}
ostream & operator<<(ostream & lhs, const vec2 & rhs)
{
	lhs << "(" << rhs.x << "," << rhs.y << ")";
	return lhs;
}

vec2 size;
vec2 r, j;
int rmat[114][114], jmat[114][114];
vec2 dir[] = {vec2(-1, -1), vec2(0, -1), vec2(1, -1), vec2(1, 0), vec2(1, 1), vec2(0, 1), vec2(-1, 1), vec2(-1, 0)};

vec2 pos;
int dist = -1;

int conv(char c)
{
	if(c == 'R' || c == 'J'){
		return 1;
	}else if(c == ' '){
		return 0;
	}else if(c == 'X'){
		return -1;
	}
}

void read()
{
	in >> size.y >> size.x;
	in.get();
	char c;
	for(int y = 1; y <= size.y; y++){
		for(int x = 1; x <= size.x; x++){
			c = in.get();
			if(c == 'R'){
				r = vec2(x, y);
			}else if(c == 'J'){
				j = vec2(x, y);
			}
			rmat[x][y] = jmat[x][y] = conv(c);
		}
		while(in.get() != '\n' && !in.eof());
	}
	rmat[j.x][j.y] = jmat[r.x][r.y] = 0;
}

void brucelee(vec2 start, int mat[114][114])
{
	queue<vec2> qu;
	qu.push(start);
	vec2 curr, neckst;
	while(!qu.empty()){
		curr = qu.front();
		qu.pop();
		for(int i = 0; i < 8; i++){
			neckst = curr;
			neckst += dir[i];
			if(neckst.in_bounds(size) && mat[neckst.x][neckst.y] == 0){
				mat[neckst.x][neckst.y] = mat[curr.x][curr.y] + 1;
				qu.push(neckst);
			}
		}
	}
}

void findy()
{
	for(int y = 1; y <= size.y; y++){
		for(int x = 1; x <= size.x; x++){
			if(rmat[x][y] == jmat[x][y] && rmat[x][y] > 0){
				if(dist == -1){
					dist = rmat[x][y];
				}else{
					dist = min(dist, rmat[x][y]);
				}
				pos = vec2(x, y);
			}
		}
	}
}

void solve()
{
	brucelee(r, rmat);
	brucelee(j, jmat);
	findy();
}

void write()
{
	out << dist << " " << pos.y << " " << pos.x;
}

int main()
{
	read();
	solve();
	write();
}