Cod sursa(job #1425044)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 26 aprilie 2015 15:16:19
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <vector>
#include <utility>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;

template <typename T>
class mat{
	T* buf;
public:
	const int n, m;
	mat(const int N, const int M):
		n(N), m(M){
		buf = new T[N*M]; }
	T& la(const int x, const int y){
		return buf[x * m + y]; }
	T& operator[](const pair<int, int>& p){
		return buf[p.first * m + p.second]; }
	const T& operator[](const pair<int, int>& p)const{
		return buf[p.first * m + p.second]; }
	void edge(const T& val){
		for(int i = 0; i < n; ++i){
			la(i, 0) = val;
			la(i, m-1) = val; }
		for(int i = 0; i < m; ++i){
			la(0, i) = val;
			la(n-1, i) = val; } } };

constexpr int gol = -3, bloc = -4, dl[] = {0, 1, 1, 1, 0, -1, -1, -1},
	dc[] = {1, 1, 0, -1, -1, -1, 0, 1};

void citeste_matrici(ifstream& f, const int n, const int m, mat<int>& mat_romeo, mat<int>& mat_julieta,
	pair<int, int>& romeo, pair<int, int>& julieta){
	char* buf = new char[m+1];
	for(int i = 1; i <= n; ++i){
		f.read(buf, m+1);
		for(int j = 1; j <= m; ++j){
			switch(buf[j]){
			case 'R':
				romeo = make_pair(i, j);
				mat_romeo.la(i, j) = gol;
				mat_julieta.la(i, j) = gol;
				break;
			case 'J':
				julieta = make_pair(i, j);
				mat_romeo.la(i, j) = gol;
				mat_julieta.la(i, j) = gol;
				break;
			case 'X':
				mat_romeo.la(i, j) = bloc;
				mat_julieta.la(i, j) = bloc;
				break;
			case ' ':
				mat_romeo.la(i, j) = gol;
				mat_julieta.la(i, j) = gol;
				break; } } }
	delete[] buf; }

void desen_1(mat<int>& mat, const pair<int, int>& st){
	queue<pair<int, int> > de_viz;
	de_viz.push(st);
	mat[st] = 0;
	pair<int, int> cur, next;
	while(!de_viz.empty()){
		cur = de_viz.front();
		de_viz.pop();
		for(int i = 0; i < 8; ++i){
			next.first = cur.first + dl[i];
			next.second = cur.second + dc[i];
			if(mat[next] == gol){
				mat[next] = mat[cur]+1;
				de_viz.push(next); } } } }

pair<int, int> desen_2(mat<int>& mat1, const pair<int, int>& st, const mat<int>& contra){
	queue<pair<int, int> > de_viz;
	de_viz.push(st);
	mat1[st] = 0;
	pair<int, int> cur, next;
	while(!de_viz.empty()){
		cur = de_viz.front();
		de_viz.pop();
		if(contra[cur] == mat1[cur]){
			return cur; }
		for(int i = 0; i < 8; ++i){
			next.first = cur.first + dl[i];
			next.second = cur.second + dc[i];
			if(mat1[next] == gol){
				mat1[next] = mat1[cur]+1;
				de_viz.push(next); } } } }

int main(){
	ifstream f("rj.in");
	int n, m;
	f >> n >> m;
	mat<int> mat_romeo(n+2, m+2), mat_julieta(n+2, m+2);
	mat_romeo.edge(bloc);
	mat_julieta.edge(bloc);
	pair<int, int> romeo, julieta;
	citeste_matrici(f, n, m, mat_romeo, mat_julieta, romeo, julieta);
	desen_1(mat_romeo, romeo);
	const auto rez = desen_2(mat_julieta, julieta, mat_romeo);
	ofstream g("rj.out");
	g << mat_romeo[rez]+1 << ' ' << rez.first << ' ' << rez.second;
	return 0; }