Pagini recente » Cod sursa (job #2362934) | Cod sursa (job #1756083) | Cod sursa (job #2524869) | Cod sursa (job #697658) | Cod sursa (job #2649989)
#include <bits/stdc++.h>
using namespace std;
ifstream in("car.in");
ofstream out("car.out");
struct poz
{
int x, y, dir;
poz(int _x, int _y, int _dir)
{
x = _x; y = _y; dir = _dir;
}
};
int dx[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dy[8] = {1, 0, -1, -1, -1, 0, 1, 1};
deque<poz> q;
int viz[505][505][8];
bool mat[505][505];
int main()
{
int n, m; in >> n >> m;
int x1, x2, y1, y2; in >> x1 >> y1 >> x2 >> y2;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
in >> mat[i][j];
for(int dir = 0; dir < 8; dir++)
viz[i][j][dir] = 1000000000;
}
for(int dir = 0; dir < 8; dir++) {
q.push_back(poz(x1, y1, dir));
viz[x1][y1][dir] = 0;
}
bool touched = 0;
while(!touched && !q.empty())
{
poz cnt = q.front(); q.pop_front();
if(cnt.x == x2 && cnt.y == y2) touched = 1;
poz new_p(0, 0, 0);
new_p.x = cnt.x + dx[cnt.dir];
new_p.y = cnt.y + dy[cnt.dir];
new_p.dir = cnt.dir;
if(mat[new_p.x][new_p.y] == 0 && viz[new_p.x][new_p.y][new_p.dir] > viz[cnt.x][cnt.y][cnt.dir])
{
viz[new_p.x][new_p.y][new_p.dir] = viz[cnt.x][cnt.y][cnt.dir];
q.push_front(new_p);
}
new_p.x = cnt.x;
new_p.y = cnt.y;
new_p.dir = (cnt.dir + 1) % 8;
if(mat[new_p.x][new_p.y] == 0 && viz[new_p.x][new_p.y][new_p.dir] > viz[cnt.x][cnt.y][cnt.dir] + 1)
{
viz[new_p.x][new_p.y][new_p.dir] = viz[cnt.x][cnt.y][cnt.dir] + 1;
q.push_back(new_p);
}
new_p.x = cnt.x;
new_p.y = cnt.y;
new_p.dir = (cnt.dir + 7) % 8;
if(mat[new_p.x][new_p.y] == 0 && viz[new_p.x][new_p.y][new_p.dir] > viz[cnt.x][cnt.y][cnt.dir])
{
viz[new_p.x][new_p.y][new_p.dir] = viz[cnt.x][cnt.y][cnt.dir] + 1;
q.push_back(new_p);
}
}
int minim = viz[x2][y2][0];
for(int dir = 0; dir < 8; dir++)
{
minim = min(minim, viz[x2][y2][dir]);
}
out << ((minim == 1000000000) ? (-1) : (minim));
}