Pagini recente » Cod sursa (job #3193420) | Cod sursa (job #1935478) | Cod sursa (job #2744383) | Cod sursa (job #1926380) | Cod sursa (job #3216626)
#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();
}
};
struct PQFast {
// sa zicem ca elementul cu distanta minima din pq-ul nostru are
// distanta = d
// atunci, elementul cu distanta maxima din pq-ul nostru are
// distanta <= d + 4
queue<pair<int, Stare>> qs[5];
int min_d_cnt = 0;
void add(Stare s, int d) {
assert(d <= min_d_cnt + 4);
qs[d % 5].push({d, s}); // acum qs[x] retine distantele %5 = x
// fiindca toate distantele sunt intr-un interval de lungime < 5
// qs[d % 5] retine toate elementele cu distanta exact egala cu = d
}
Stare pop() {
while(qs[min_d_cnt % 5].empty()) {
min_d_cnt++;
}
auto p = qs[min_d_cnt % 5].front();
qs[min_d_cnt % 5].pop();
return p.second;
}
bool empty() {
bool ok = true;
for(int i = 0; i < 5; i++) {
ok &= qs[i].empty();
}
return ok;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
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];
}
}
PQFast 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]);
}
if(minim == infty) minim = -1;
cout << minim << '\n';
}