Pagini recente » Cod sursa (job #3361461) | Cod sursa (job #3361761) | Cod sursa (job #3361987) | Monitorul de evaluare | Cod sursa (job #3361288)
#include <fstream>
#include <deque>
#define int long long
using namespace std;
ifstream cin ("car.in");
ofstream cout ("car.out");
const int INF=1e18;
int di[]={-1,-1,0,1,1,1,0,-1};
int dj[]={0,1,1,1,0,-1,-1,-1};
int n,m;
int si,sj,fi,fj;
int a[505][505];
int dist[505][505][8];
struct State {
int r,c,dir;
};
int cost(int d1, int d2) {
int diff=abs(d1-d2);
if (diff>4) diff=8-diff;
return diff;
}
signed main() {
cin>>n>>m;
cin>>si>>sj>>fi>>fj;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
cin>>a[i][j];
for (int d=0; d<8; ++d) {
dist[i][j][d]=INF;
}
}
}
if (si==fi && sj==fj) {
cout<<0;
return 0;
}
deque<State> dq;
for (int d=0; d<8; ++d) {
int ni=si+di[d];
int nj=sj+dj[d];
if (ni>=1 && ni<=n && nj>=1 && nj<=m && a[ni][nj]==0) {
dist[ni][nj][d]=0;
dq.push_back({ni, nj, d});
}
}
while (!dq.empty()) {
State cur=dq.front();
dq.pop_front();
for (int d=0; d<8; ++d) {
int ni=cur.r+di[d];
int nj=cur.c+dj[d];
if (ni>=1 && ni<=n && nj>=1 && nj<=m && a[ni][nj]==0) {
int w=cost(cur.dir, d);
if (dist[ni][nj][d]>dist[cur.r][cur.c][cur.dir]+w) {
dist[ni][nj][d]=dist[cur.r][cur.c][cur.dir]+w;
if (w==0) {
dq.push_front({ni, nj, d});
} else {
dq.push_back({ni, nj, d});
}
}
}
}
}
int ans=INF;
for (int d=0; d<8; ++d) {
if (dist[fi][fj][d]<ans) {
ans=dist[fi][fj][d];
}
}
if (ans==INF) {
cout<<-1;
} else {
cout<<ans;
}
}