Cod sursa(job #2923570)

Utilizator RaresPoinaruPoinaru-Rares-Aurel RaresPoinaru Data 15 septembrie 2022 21:32:56
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("car.in");
ofstream fout ("car.out");

const int MAXN=510;
const int MAXD=9;
const int INF=2e9;

struct elem{
    int cost,x,y,s;
};

int n,m,a[MAXN][MAXN],posi,posj,posfi,posfj,dp[MAXD][MAXN][MAXN];
bool visit[MAXD][MAXN][MAXN];
deque <elem> dq;
int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};

bool Seafla (int i, int j){
    if (i>=1 and i<=n and j>=1 and j<=m and a[i][j]==0)
        return true;
    return false;
}

void solve (){
    while (dq.empty ()==false){
        int costcrt=dq.front ().cost,i=dq.front ().x,j=dq.front ().y,sens=dq.front ().s;
        dq.pop_front ();

        if (visit[sens][i][j]==1)continue;
        visit[sens][i][j]=1;
        int nextsens=sens;
        int ki=i+dx[nextsens],kj=j+dy[nextsens];
        if (Seafla (ki,kj)==true){
            if (costcrt<dp[nextsens][ki][kj]){
                dp[nextsens][ki][kj]=costcrt;
                dq.push_front ({costcrt,ki,kj,nextsens});
            }
        }
        nextsens=(sens+1)%8;
        if(costcrt+1<dp[nextsens][i][j]){
            dp[nextsens][i][j]=costcrt+1;
            dq.push_back({costcrt+1,i,j,nextsens});
        }
        nextsens=(sens-1+8)%8;
        if(costcrt+1<dp[nextsens][i][j]){
            dp[nextsens][i][j]=costcrt+1;
            dq.push_back({costcrt+1,i,j,nextsens});
        }
    }
    int rez=INF;
    for (int i=0;i<8;++i){
        rez=min (rez,dp[i][posfi][posfj]);
    }
    if (rez==INF)
        fout <<-1;
    else
        fout <<rez;
}

int main()
{
    fin >>n>>m;
    fin >>posi>>posj>>posfi>>posfj;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            fin >>a[i][j];
            for (int k=0;k<8;++k)
                dp[k][i][j]=INF;
        }
    }

    for (int i=0;i<8;++i){
        dq.push_back ({0,posi,posj,i});
        dp[i][posi][posj]=0;
    }
    solve ();
    fin.close ();
    fout.close ();
    return 0;
}