Cod sursa(job #3361288)

Utilizator Zeno1789Zeno Ciuca Zeno1789 Data 22 iulie 2026 20:20:08
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#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;
    }
}