Pagini recente » Cod sursa (job #2394967) | Cod sursa (job #2097366) | Cod sursa (job #584295) | Cod sursa (job #1965645) | Cod sursa (job #2649984)
#include <bits/stdc++.h>
using namespace std;
ifstream in("car.in");
ofstream out("car.out");
int viz[505][505][8];
bool mat[505][505];
/*
4 - 5 - 6
3 - x - 7
2 - 1 - 0
*/
int dx[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dy[8] = {1, 0, -1, -1, -1, 0, 1, 1};
queue<pair<int /*-cost*/, pair<int, int> /*poz*/>> pq;
int abs(int x) {
return max(x, -x);
}
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 <= m; j++)
{
in >> mat[i][j];
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int dir = 0; dir < 8; dir++)
viz[i][j][dir] = 1000000000;
for(int dir = 0; dir < 8; dir++)
{
viz[x1][y1][dir] = 0;
pq.push(make_pair(-0, make_pair(x1, y1)));
}
bool touched = 0;
while(!touched && !pq.empty())
{
auto cnt = pq.front(); pq.pop();
if(cnt.second.first == x2 && cnt.second.second == y2)
touched = 1;
for(int dir = 0; dir < 8; dir++)
{
for(int chdir = -3; chdir <= 4; chdir++)
{
int new_x, new_y, new_dir;
new_dir = (dir + 8 + chdir) % 8;
new_x = cnt.second.first + dx[new_dir];
new_y = cnt.second.second + dy[new_dir];
if(mat[new_x][new_y] == 0 && viz[new_x][new_y][new_dir] > viz[cnt.second.first][cnt.second.second][dir] + abs(chdir))
{
viz[new_x][new_y][new_dir] = viz[cnt.second.first][cnt.second.second][dir] + abs(chdir);
pq.push(make_pair(-(viz[cnt.second.first][cnt.second.second][dir] + abs(chdir)), make_pair(new_x, new_y)));
}
}
}
}
//cout << viz[4][4][6] << endl;
int minim = viz[x2][y2][0];
for(int dir = 0; dir < 8; dir++)
minim = min(minim, viz[x2][y2][dir]);
out << minim;
}