Pagini recente » Cod sursa (job #665558) | Cod sursa (job #3002796) | Cod sursa (job #3284606) | Cod sursa (job #2979723) | Cod sursa (job #3211610)
#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;
}
}
}
}
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);
}