Pagini recente » Cod sursa (job #374012) | Cod sursa (job #3211597)
#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);
}