Pagini recente » Cod sursa (job #778742) | Cod sursa (job #2101488) | Cod sursa (job #1472831) | Cod sursa (job #1216446) | Cod sursa (job #2139918)
#include <iostream>
#include <fstream>
#include <queue>
#define dimm 505
#define mval 1000005
std::ifstream f("car.in");
std::ofstream g("car.out");
int N, M, zid[dimm][dimm];
int y0, x0, y1, x1;
int curba(int d1, int d2) {
int v;
if(d1==d2+4) v=4;
else if(d2==d1+4) v=4;
else v = std::max((d1-d2)%4, (d2-d1)%4);
return v;
}
int cost[dimm][dimm];
struct nod {int y, x, dir;};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}, dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
void totul_are_un_cost() {
std::queue <nod> q;
q.push({y0, x0, 0});
for (int i=1, j; i<=N; i++)
for (j=1; j<=M; j++)
cost[i][j] = mval;
nod pres, nou;
cost[y0][x0] = 0;
pres = q.front();
for (int i=0; i<8; i++) {
nou = pres; nou.dir = i;
nou.y += dy[i]; nou.x += dx[i];
int c = 0;
if(!zid[nou.y][nou.x] && (cost[nou.y][nou.x] > cost[pres.y][pres.x] + c)) {
cost[nou.y][nou.x] = cost[pres.y][pres.x] + c;
q.push(nou);
}
}
while(!q.empty()) {
pres = q.front();
q.pop();
for (int i=0; i<8; i++) {
nou = pres; nou.dir = i;
nou.y += dy[i]; nou.x += dx[i];
int c = curba(nou.dir, pres.dir);
if(!zid[nou.y][nou.x] && (cost[nou.y][nou.x] > cost[pres.y][pres.x] + c)) {
cost[nou.y][nou.x] = cost[pres.y][pres.x] + c;
q.push(nou);
}
}
}
}
void citire() {
f >> N >> M;
f >> y0 >> x0 >> y1 >> x1;
for (int i=0, j; i<N; i++)
for (j=0; j<M; j++)
f >> zid[i+1][j+1];
}
void rezolvare() {
totul_are_un_cost();
if(cost[y1][x1] == mval) cost[y1][x1] = -1;
g << cost[y1][x1];
}
int main()
{
citire();
rezolvare();
return 0;
}