Cod sursa(job #3211564)

Utilizator CalibrixkngIordache Andrei Calibrixkng Data 9 martie 2024 15:18:59
Problema Car Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.57 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[2][NMAX * NMAX];
struct muchie {
	int second, cost;
};
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[0][i] << " ";
	}
	cout << "\nnr pasi:";
	for (int i = 2; i <= index; i++) {
		cout << viz[1][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]});
				}
			}
			
		}
}
void bfs(int target) {
	queue<int> q;
	for (int i = 2; i <= index; i++)
		viz[0][i] = -1;
	q.push(target);
	viz[0][target] = 0;
	viz[1][target] = 0;
	while (!q.empty()) {
		int node = q.front();
		for (auto e : graf[node]) {
			if (viz[1][node] == 0 && viz[0][node]==0) {
				viz[0][e.second] = e.cost;
				viz[1][e.second] = 0;
				q.push(e.second);
			}
			else if (viz[0][e.second] == -1)
			{
				viz[0][e.second] = e.cost;
				int op = viz[0][node];
				int os = e.cost;
				int increment = 0;
				int value = abs(op + os);
				increment = 4 - value;
				viz[1][e.second] = viz[1][node] + increment;
				q.push(e.second);

			}		}
		q.pop();
	}
}
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);
		}
	}
	bfs(mat[start.x][start.y]);
	//afisare();
	g <<( viz[1][mat[ionel.x][ionel.y]]==-1? viz[1][mat[ionel.x][ionel.y]]: -1);
}