Pagini recente » Cod sursa (job #1502232) | Cod sursa (job #1987340) | Cod sursa (job #2914963) | Cod sursa (job #2642881) | Cod sursa (job #3340381)
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define pb push_back
using namespace std;
//#define MOD 1999999973
int n, m;
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
bool inmat(int x, int y) {
if (1 <= x && x <= n && 1 <= y && y <= m) return true;
return false;
}
struct state {
int x, y;
int dir;
int cost;
state (){
dir = -1;
cost = 0;
}
bool operator>(const state &other) const {
return cost > other.cost;
}
};
int find_diff(int a, int b) {
int x = min (abs(a - b), abs(8 - abs(a - b)));
return x;
}
signed main(){
ifstream cin ("car.in");
ofstream cout ("car.out");
cin >> n >> m;
int s1, s2, e1 ,e2;
cin >> s1 >> s2 >> e1 >> e2;
vector < vector <int>> a(n + 2, vector <int>(m + 2, 0));
vector <vector <vector <int>>> dist(n + 2, vector <vector <int>>(m + 2, vector <int>(8, 1e9)));
for (int i=1;i <= n;i++) {
for (int j=1;j <= m;j++) {
cin >> a[i][j];
}
}
priority_queue <state, vector<state>, greater<state>> q;
state aux;
aux.x = s1;
aux.y = s2;
for (int d=0;d < 8;d++) {
aux.dir = d;
q.push(aux);
dist[s1][s2][d] = 0;
}
while (!q.empty()) {
aux = q.top();
q.pop();
int x = aux.x;
int y = aux.y;
int dir = aux.dir;
for (int d=0;d < 8;d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (inmat(nx, ny) && a[nx][ny] == 0 && dist[x][y][dir] + find_diff(dir, d) < dist[nx][ny][d]) {
dist[nx][ny][d] = dist[x][y][dir] + find_diff(dir, d);
aux.x = nx;
aux.y = ny;
aux.dir = d;
aux.cost = dist[x][y][dir] + find_diff(dir, d);
q.push(aux);
}
}
}
int minn = 1e9;
for (int d=0;d < 8;d++) minn = min (minn , dist[e1][e2][d]);
if (minn == 1e9) cout << -1 << "\n";
else cout << minn << "\n";
return 0;
}