Pagini recente » Cod sursa (job #3339896) | Cod sursa (job #3340665) | Cod sursa (job #2963989) | Cod sursa (job #3349458) | Cod sursa (job #3340384)
#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;
state (){
dir = -1;
}
};
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];
}
}
deque<state> dq;
state aux;
aux.x = s1;
aux.y = s2;
for (int d = 0; d < 8; d++) {
dist[s1][s2][d] = 0;
aux.dir = d;
dq.push_back(aux);
}
while (!dq.empty()) {
aux = dq.front();
dq.pop_front();
int x = aux.x;
int y = aux.y;
int dir = aux.dir;
int costi = dist[x][y][dir];
int nx = x + dx[dir];
int ny = y + dy[dir];
if (inmat(nx, ny) && a[nx][ny] == 0) {
if (dist[nx][ny][dir] > costi) {
dist[nx][ny][dir] = costi;
aux.x = nx;
aux.y = ny;
dq.push_front(aux);
}
}
int opt1 = (dir + 1) % 8;// 1 cost | ^ 0 cost
int opt2 = (dir + 7) % 8;
if (dist[x][y][opt1] > costi + 1) {
dist[x][y][opt1] = costi + 1;
aux.x = x; aux.y = y;
aux.dir = opt1;
dq.push_back(aux);
}
if (dist[x][y][opt2] > costi + 1) {
dist[x][y][opt2] = costi + 1;
aux.x = x; aux.y = y;
aux.dir = opt2;
dq.push_back(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;
}