Pagini recente » Cod sursa (job #2046936) | Cod sursa (job #2903478) | Cod sursa (job #1829890) | Cod sursa (job #1337288) | Cod sursa (job #2140138)
#include <iostream>
#include <fstream>
#include <climits>
#include <deque>
#define dimm 505
#define dirs 8
#define mval INT_MAX
std::ifstream f("car.in");
std::ofstream g("car.out");
int N, M, zid[dimm][dimm];
int y0, x0, y1, x1;
int cost[dimm][dimm][dirs];
int grad[] = {7, 1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}, dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
int totul_are_un_cost() {
for (int i=1, j, k; i<=N; i++)
for (j=1; j<=M; j++)
for (k=0; k<dirs; k++)
cost[i][j][k] = mval;
struct nod {int y, x, dir;};
std::deque <nod> dq;
for (int i=0; i<dirs; i++) {
cost [y0][x0][i] = 0;
dq.push_back({y0, x0, i});
}
nod pres, nou;
while(!dq.empty()) {
pres = dq.front();
dq.pop_front();
if(pres.y == y1 && pres.x == x1)
return cost[y1][x1][pres.dir];
//varianta preferabila: ne continuam directia
nou = pres; nou.y += dy[pres.dir]; nou.x += dx[pres.dir];
if(!zid[nou.y][nou.x] && cost[nou.y][nou.x][nou.dir] > cost[pres.y][pres.x][pres.dir])
dq.push_front(nou), cost[nou.y][nou.x][nou.dir] = cost[pres.y][pres.x][pres.dir];
//treceri intre directii
for (int i=0; i<2; i++) {
int v = grad[i];
nou = pres; int d = (pres.dir + v)%dirs;
nou.dir = d;
if(!zid[nou.y][nou.x] && cost[nou.y][nou.x][nou.dir] > cost[pres.y][pres.x][pres.dir] + 1)
dq.push_back(nou), cost[nou.y][nou.x][nou.dir] = cost[pres.y][pres.x][pres.dir] + 1;
}
} return -1;
}
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() {
g << totul_are_un_cost();
}
int main()
{
citire();
rezolvare();
return 0;
}