Pagini recente » Cod sursa (job #108142) | Cod sursa (job #206254) | Cod sursa (job #575006) | Cod sursa (job #3218126) | Cod sursa (job #2675750)
#include <fstream>
#include <queue>
#include <climits>
using namespace std;
const int NMAX = 500;
const int MMAX = 500;
bool liber[2 + NMAX][2 + MMAX];
int cost[1 + NMAX][1 + MMAX];
int dx[] = {0,-1,-1,-1, 0, 1,1,1};
int dy[] = {1, 1, 0,-1,-1,-1,0,1};
priority_queue<pair<pair<int ,int>, pair<int, int>>, vector<pair<pair<int, int>, pair<int, int>>>, greater<pair<pair<int, int>, pair<int, int>>>> pq;
void dijkstra(int xs, int ys)
{
pq.push(make_pair(make_pair(0, -1), make_pair(xs, ys)));
while (!pq.empty())
{
int x = pq.top().second.first;
int y = pq.top().second.second;
int cost_ = pq.top().first.first;
int dir = pq.top().first.second;
pq.pop();
if (cost_ > cost[x][y]) continue;
for (int i = 0; i < 8; i++)
{
int xVecin = x + dx[i];
int yVecin = y + dy[i];
if (liber[xVecin][yVecin])
{
int newDir;
if (dir == -1)
{
newDir = i;
}
else
{
newDir = dir;
}
int minim;
if (abs(newDir - i) < abs(i + 8 - newDir))
{
minim = abs(newDir - i);
}
else
{
minim = abs(i + 8 - newDir);
}
if (cost_ + minim < cost[xVecin][yVecin])
{
cost[xVecin][yVecin] = cost_ + minim;
pq.push(make_pair(make_pair(cost_ + minim, newDir), make_pair(xVecin, yVecin)));
}
}
}
}
}
int main()
{
ifstream in("car.in");
ofstream out("car.out");
int n, m;
int xs, ys, xf, yf;
in >> n >> m;
in >> xs >> ys >> xf >> yf;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
in >> liber[i][j];
liber[i][j] = !liber[i][j];
cost[i][j] = INT_MAX;
}
}
cost[xs][ys] = 0;
dijkstra(xs, ys);
out << cost[xf][yf] << '\n';
return 0;
}