Pagini recente » Cod sursa (job #3265294) | Cod sursa (job #270526) | Cod sursa (job #1030651) | Cod sursa (job #537660) | Cod sursa (job #2724071)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin ("car.in");
ofstream fout ("car.out");
const int ct = 100000;
const int inf = 1e9;
int dist[502][502][8], n, m, v[502][502];
int dl[] = {0, 0, -1, -1, -1, 1, 1, 1};
int dc[] = {-1, 1, 0, -1, 1, 0, -1, 1};
struct lol {
int dist, x, y, dir;
};
struct cmp {
bool operator () (const lol &a, const lol &b) {
return a.dist > b.dist;
}
};
bool lol1 (int x, int y) {
return (x >= 1 && x <= n && y >= 1 && y <= m && !v[x][y]);
}
int main ()
{
fin >> n >> m;
int x1, y1, x2, y2;
fin >> x1 >> y1 >> x2 >> y2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
fin >> v[i][j];
priority_queue<lol, vector<lol>, cmp>pq;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 0; k < 8; k++)
dist[i][j][k] = inf;
for (int i = 0; i < 8; i++) {
dist[x1][y1][i] = 0;
pq.push({0, x1, y1, i});
}
while (pq.size()) {
auto p = pq.top();
pq.pop();
if (p.dist != dist[p.x][p.y][p.dir])
continue;
for (int i = 0; i < 8; i++) {
int i1 = p.x + dl[i];
int j1 = p.y + dc[i];
if (lol1(i1, j1) && dist[i1][j1][i] > p.dist + abs(dl[p.dir] - dl[i]) + abs(dc[p.dir] - dc[i])) {
dist[i1][j1][i] = p.dist + abs(dl[p.dir] - dl[i]) + abs(dc[p.dir] - dc[i]);
pq.push({dist[i1][j1][i], i1, j1, i});
}
}
}
int ans = inf;
for (int i = 0; i < 8; i++)
ans = min(ans, dist[x2][y2][i]);
fout << ans;
return 0;
}