Cod sursa(job #3211597)

Utilizator CalibrixkngIordache Andrei Calibrixkng Data 9 martie 2024 17:00:32
Problema Car Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");

const int NMAX = 5e2;
struct muchie {
	int second, cost;
};
int viz[NMAX * NMAX],pasi[NMAX*NMAX];
struct pos {
	int x, y;
}start,ionel;
vector<muchie> graf[NMAX * NMAX];

int mat[NMAX][NMAX],index=1,n,m;
bool inside(int x, int y) {
	return x > 0 && y > 0 && x <= n && y <= m;
}
void index_fill(int x, int y, int val) {

}
void citire() {
	f >> n >> m;
	f >> start.x >> start.y >> ionel.x >> ionel.y;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= m; j++) {
			f >> mat[i][j];
			if (mat[i][j] == 0)
				mat[i][j] = ++index;
		}
}
void afisare() {
	cout << "AFISARE MATRICE:" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << mat[i][j] << " ";
		}
		cout << endl;
	}
	cout << "AFISARE GRAF:" << endl;
	for (int i = 2; i <= index; i++) {
		cout << i <<":" << endl;
		for (auto j : graf[i])
			cout << j.second << " "<<j.cost<<", ";
		cout << "\n";
	}
	cout << "AFISARE DRUMURI:\n orientare:" << endl;
	for (int i = 2; i <= index; i++) {
		cout << viz[i] << " ";
	}
	cout << "\nnr pasi:";
	for (int i = 2; i <= index; i++) {
		cout << viz[i] << " ";
	}
	
}
void add(int x, int y) {
	int node = mat[x][y];
	int dx[] = { -1,0,1 };
	int dy[] = { -1,0,1 };
	for(int i=0;i<3;i++)
		for (int j = 0; j < 3; j++) {
			int new_x = x + dx[i];
			int new_y = y + dy[j];
			if (inside(new_x, new_y)) {
				if (mat[new_x][new_y] != 1 && mat[new_x][new_y]!=mat[x][y]) {
					graf[node].push_back({ mat[new_x][new_y],dx[i]  + dy[j]});
				}
			}
			
		}
}
int increment(int a, int b) {
	int increment = 0;
	int value = abs(a + b);
	increment = 4 - value;
	if (increment == 4)increment = 0;
	else if (a == 0 || b == 0) {
		increment = abs(a + b);
	}
	return increment;
}

void calculate_costuri() {
	int node_start = mat[start.x][start.y];
	queue<int> q,ori;
	for (int i = 2; i <= index; i++)
		viz[i] = -1;
	viz[node_start] = 0;

	q.push(node_start);
	ori.push(-2);
	while (!q.empty()) {
		int node = q.front();
		int ori_p = ori.front();
		q.pop();
		ori.pop();
		for (auto e : graf[node]) {
			if (viz[e.second] == -1) {
				//daca nu am mai fost in nod
				q.push(e.second);
				ori.push(e.cost);
				int ori_c = e.cost;
				int l = increment(ori_p, ori_c);
				viz[e.second] = viz[node] + l;
			}
			else if (viz[e.second] > increment(ori_p, e.cost)+viz[node]) {
				q.push(e.second);
				ori.push(e.cost);
				int ori_c = e.cost;
				int l = increment(ori_p, ori_c);
				viz[e.second] = viz[node] + l;
			}
		}

	}

}
int main() {
	citire();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (mat[i][j] != 1)
				add(i, j);
		}
	}
	calculate_costuri();
	g <<( viz[mat[ionel.x][ionel.y]]!=-1? viz[mat[ionel.x][ionel.y]]: -1);
}