Pagini recente » Cod sursa (job #2872834) | Cod sursa (job #443465) | Cod sursa (job #510137) | Cod sursa (job #3211576)
#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]});
}
}
}
}
int increment(int a, int b) {
int increment = 0;
int value = abs(a + b);
increment = 4 - value;
if (increment == 4)increment = 0;
return increment;
}
void bfs(int target) {
queue<int> q;
for (int i = 2; i <= index; i++)
viz[1][i] = -2;
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[1][e.second] == -2)
{
viz[0][e.second] = e.cost;
int l = increment(viz[0][node], e.cost);
viz[1][e.second] = viz[1][node] + l;
q.push(e.second);
}
else if (viz[1][e.second] != -2 && viz[1][e.second] > viz[1][node] + increment(viz[0][node], e.cost)) {
viz[1][e.second] = viz[1][node] + increment(viz[0][node], e.cost);
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]);
g <<( viz[1][mat[ionel.x][ionel.y]]!=-1? viz[1][mat[ionel.x][ionel.y]]: -1);
}