Cod sursa(job #2634834)

Utilizator rebecca0312Andrei Rebecca rebecca0312 Data 12 iulie 2020 13:50:34
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include<bits/stdc++.h>
using namespace std;

const int NMAX=505;
const int INF=2000000000;

const int dx[]={-1,-1,0,1,1,1,0,-1};
const int dy[]={0,1,1,1,0,-1,-1,-1};

int n,m,Si,Sj,Fi,Fj,ans;
int a[NMAX][NMAX],dp[NMAX][NMAX][10];

struct el{
    int x,y,dir,cost;
};

queue<el> q0,q1;

inline bool ok(int i, int j){
    if(i<1 || j<1 || i>n || j>m || a[i][j])
        return false;
    return true;
}

inline void read(){
    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &Si, &Sj, &Fi, &Fj);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d", &a[i][j]);
            for(int k=0;k<8;k++)
                dp[i][j][k]=INF;
        }
    for(int k=0;k<8;k++){
        el temp;
        temp.x=Si,temp.y=Sj;
        temp.cost=0;
        temp.dir=k;
        q0.push(temp);
    }
}

inline void dijkstra(){
    while(!q0.empty()){
        while(!q0.empty()){
            el temp=q0.front(),temp1;
            q0.pop();
            temp1.cost=temp.cost, temp1.dir=temp.dir;
            temp1.x=temp.x+dx[temp.dir];
            temp1.y=temp.y+dy[temp.dir];
            if(ok(temp1.x, temp1.y) && dp[temp1.x][temp1.y][temp1.dir]>temp1.cost){
                dp[temp1.x][temp1.y][temp1.dir]=temp1.cost;
                q0.push(temp1);
            }
            temp1.cost++;
            temp1.dir=(temp.dir+1)%8;
            temp1.x=temp.x;
            temp1.y=temp.y;
            if(ok(temp1.x, temp1.y) && dp[temp1.x][temp1.y][temp1.dir]>temp1.cost){
                q1.push(temp1);
                dp[temp1.x][temp1.y][temp1.dir]=temp1.cost;
            }
            temp1.dir=(temp.dir-1);
            if(temp1.dir<0)
                temp1.dir=7;
            if(ok(temp1.x, temp1.y) && dp[temp1.x][temp1.y][temp1.dir]>temp1.cost){
                q1.push(temp1);
                dp[temp1.x][temp1.y][temp1.dir]=temp1.cost;
            }
        }
        while(!q1.empty()){
            el temp=q1.front();
            q1.pop();
            q0.push(temp);
        }
    }
}

int main(){
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    read();
    dijkstra();
    int ans=dp[Fi][Fj][0];
    for(int d=1;d<8;d++)
        ans=min(ans, dp[Fi][Fj][d]);
    if(ans==INF)
        printf("-1");
    else
        printf("%d", ans);
    return 0;
}