Pagini recente » Cod sursa (job #70681) | Cod sursa (job #2730103) | Cod sursa (job #1332908) | Cod sursa (job #1086534) | Cod sursa (job #3216623)
#include <bits/stdc++.h>
using namespace std;
ifstream in("car.in");
#define cin in
ofstream out("car.out");
#define cout out
const int nmax = 505;
const int dmax = 8;
const int infty = 1e9;
int dist[nmax][nmax][dmax];
int mat[nmax][nmax];
/*
567
4x0
321
*/
int dx[] = {0, +1, +1, +1, 0, -1, -1, -1};
int dy[] = {+1, +1, 0, -1, -1, -1, 0, +1};
struct Stare {
int x, y, d;
bool operator<(const Stare &other) const {
if(x != other.x) return x < other.x;
if(y != other.y) return y < other.y;
return d < other.d;
}
};
struct PQSlow {
priority_queue<pair<int, Stare>> pq;
void add(Stare s, int d) {
pq.push({-d, s}); // punem cu - fiindca priority_queue e max-heap
}
Stare pop() {
Stare s = pq.top().second;
pq.pop();
return s;
}
bool empty() {
return pq.empty();
}
};
int main() {
for(int i = 0; i < nmax; i++) {
for(int j = 0; j < nmax; j++) {
for(int k = 0; k < dmax; k++) {
dist[i][j][k] = infty;
}
}
}
int n, m; cin >> n >> m;
int sx, sy, fx, fy; cin >> sx >> sy >> fx >> fy;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> mat[i][j];
}
}
PQSlow pq;
for(int d = 0; d < dmax; d++) {
dist[sx][sy][d] = 0;
pq.add({sx, sy, d}, 0);
}
while(!pq.empty()) {
auto stare = pq.pop();
int x = stare.x;
int y = stare.y;
int dir = stare.d;
int cnt_dist = dist[x][y][dir];
// Prima oara, incercam sa ne rotim!
for(int new_dir = 0; new_dir < dmax; new_dir++) {
if(new_dir == dir) continue;
int dif = abs(dir - new_dir);
int new_dist = cnt_dist + min(dif, 8 - dif);
if(new_dist < dist[x][y][new_dir]) {
dist[x][y][new_dir] = new_dist;
pq.add({x, y, new_dir}, new_dist);
}
}
// A doua oara, incercam sa ne ducem in directia in care ne uitam!
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx <= 0 || nx > n || ny <= 0 || ny > m) continue; // Iesim din matrice
if(mat[nx][ny] == 1) continue; // Nu avem voie pe aceasta pozitie (are 1)
int new_dist = cnt_dist + 0;
if(new_dist < dist[nx][ny][dir]) {
dist[nx][ny][dir] = new_dist;
pq.add({nx, ny, dir}, new_dist);
}
}
int minim = infty;
for(int d = 0; d < dmax; d++) {
minim = min(minim, dist[fx][fy][d]);
}
cout << minim << '\n';
}