Cod sursa(job #3211606)

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

const int NMAX = 5e2;
int viz[NMAX * NMAX],pasi[NMAX*NMAX];
struct pos {
	int x, y;
}start,ionel;
struct muchie {
	int second;
	pos p;
};
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.p.x+j.p.y << ", ";
		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(pos a, pos b) {
	int inc = 0;
	if (a.x == -b.y && b.x == -a.y)
		return 0;
	while (a.x != b.x) {
		if (a.x < b.x) {
			inc++;
			a.x++;
		}
		else {
			inc++;
			b.x++;
		}
	}
	while (a.y != b.y) {
		if (a.y < b.y) {
			inc++;
			a.y++;
		}
		else {
			inc++;
			b.y++;
		}
	}
	return inc;
}

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

	q.push(node_start);
	ori.push(start);
	while (!q.empty()) {
		int node = q.front();
		pos ori_p = ori.front();
		q.pop();
		ori.pop();
		for (auto e : graf[node]) {
			if (viz[e.second] == -1) {
				q.push(e.second);
				ori.push(e.p);
				pos ori_c = e.p;
				int l = increment(ori_p, ori_c);
				viz[e.second] = viz[node] + l;
			}
			else if (viz[e.second] > increment(ori_p, e.p)+viz[node]) {
				q.push(e.second);
				ori.push(e.p);
				pos ori_c = e.p;
				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);
}