Cod sursa(job #1446292)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 1 iunie 2015 12:42:51
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.53 kb
#include <fstream>
#include <stack>
#include <array>
#include <vector>
#include <tuple>
#include <limits>
#include <utility>
#include <string>
#include <iostream>
using namespace std;

constexpr int dx[] = {0, 1, 1, 1, 0, -1, -1, -1},
	dy[] = {1, 1, 0, -1, -1, -1, 0, 1},
	gol = numeric_limits<int>::max(), bloc = -4;

class mat{
	vector<array<int, 8> > v;
	int n, m;
public:
	mat(const int N, const int M):
		v(N*M),
		n(N),
		m(M){}
	void resize(const int N, const int M){
		v.resize(N*M);
		n = N;
		m = M; }
	int& operator[](const tuple<int, int, int>& p){
		return v[get<0>(p) * m + get<1>(p)][get<2>(p)]; }
	int& la(const int a, const int b, const int c){
		return v[a * m + b][c]; }
	void print(){
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < m; ++j){
				cout << "(";
				for(int k = 0; k < 8; ++k){
					switch(la(i, j, k)){
					case gol:
						cout << "g ";
						break;
					case bloc:
						cout << "b ";
						break;
					default:
						cout << la(i, j, k) << ' ';
						break; } }
				cout << ") "; }
			cout << '\n'; } }
	void edge(const int val){
		for(int i = 0; i < n; ++i){
			for(int k = 0; k < 8; ++k){
				la(i, 0, k) = val;
				la(i, m-1, k) = val; } }
		for(int i = 0; i < m; ++i){
			for(int k = 0; k < 8; ++k){
				la(0, i, k) = val;
				la(m-1, i, k) = val; } } } };

	
int delta_unghi(const int a, const int b){
	return (a < b) ? min(b-a, 8-b+a) : min(a-b, 8-a+b); }

using coord = tuple<int, int, int>;

class mypq{
	vector<stack<coord> > v;
	int cur = 0;
	void clear(){
		while(cur < v.size() && v[cur].empty()){
			++cur; } }
public:
	void resize(const int sz){
		v.resize(sz); }
	pair<coord, int> top(){
		clear();
		return make_pair(v[cur].top(), cur); }
	bool empty(){
		clear();
		return cur == v.size(); }
	void pop(){
		clear();
		v[cur].pop(); }
	void push(const pair<coord, int>& p){
		v[p.second].push(p.first); }
	void emplace(const coord a, const int b){
		v[b].push(a); } };
	
void citeste_date(mat& harta, mypq& de_viz, int& finl, int& finc){
	ifstream f("car.in");
	int n, m, stl, stc;
	f >> n >> m >> stl >> stc >> finl >> finc >> ws;
	harta.resize(n+2, m+2);
	harta.edge(bloc);
	de_viz.resize(4*n*m + 1);
	for(int i = 0; i < 8; ++i){
		de_viz.emplace(make_tuple(stl, stc, i), 0); }
	string buf(2*m, 0);
	for(int i = 0; i < n; ++i){
		f.read(&buf[0], 2*m);
		for(int j = 0; j < m; ++j){
			switch(buf[2*j]){
			case '0':
				for(int k = 0; k < 8; ++k){
					harta.la(i+1, j+1, k) = gol; }
				break;
			case '1':
				for(int k = 0; k < 8; ++k){
					harta.la(i+1, j+1, k) = bloc; }
				break; } } }
	for(int i = 0; i < 8; ++i){
		harta.la(stl, stc, i) = 0; } }

void fa_dijkstra(mat& harta, mypq& de_viz, const int finl, const int finc){
	pair<coord, int> cur, next;
	while(!de_viz.empty()){
		cur = de_viz.top();
		de_viz.pop();
		if(get<0>(cur.first) == finl && get<1>(cur.first) == finc){
			return; }
		if(harta[cur.first] == cur.second){
			for(int i = 0; i < 8; ++i){
				next.first = make_tuple(
					get<0>(cur.first) + dx[i],
					get<1>(cur.first) + dy[i],
					i);
				next.second = cur.second + delta_unghi(get<2>(cur.first), i);
				if(harta[next.first] != bloc &&
					harta[next.first] > next.second){
					harta[next.first] = next.second;
					de_viz.push(next); } } } } }

int main(){
	mat harta(0, 0);
	mypq de_viz;
	int finl, finc;
	citeste_date(harta, de_viz, finl, finc);
	fa_dijkstra(harta, de_viz, finl, finc);
	harta.print();
	ofstream g("car.out");
	int rez = gol;
	for(int i = 0; i < 8; ++i){
		if(harta.la(finl, finc, i) != bloc){
			rez = min(rez, harta.la(finl, finc, i)); } }
	g << (rez == gol ? -1 : rez) << '\n';
	return 0; }