Cod sursa(job #1009807)

Utilizator assa98Andrei Stanciu assa98 Data 13 octombrie 2013 21:11:48
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;

const int MAX_N=510;
const int INF=1000000000;

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

struct nod {
    int x,y,d;
    nod() {
        x=y=d=0;
    }
    nod(int a,int b,int c) {
        x=a;
        y=b;
        d=c;
    }
};

inline nod turnL(nod a) {
    a.d--;
    if(a.d==-1) {
        a.d=7;
    }
    return a;
}

inline nod turnR(nod a) {
    a.d++;
    if(a.d==8) {
        a.d=0;
    }
    return a;
}

inline nod adv(nod a) {
    a.x+=dx[a.d];
    a.y+=dy[a.d];
    return a;
}

int x[MAX_N][MAX_N];
int dr[MAX_N][MAX_N][8];
bool viz[MAX_N][MAX_N][8];


int N,M;
inline bool inborder(nod a) {
    return a.x>=1&&a.x<=N&&a.y>=1&&a.y<=M&&!x[a.x][a.y];
}


deque<nod> Q;
void initializare(int x,int y) {
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=M;j++) {
            for(int d=0;d<8;d++) {
                dr[i][j][d]=INF;
            }
        }
    }
    for(int d=0;d<8;d++) {
        dr[x][y][d]=0;
        Q.push_back(nod(x,y,d));
    }
}

void dijkstra() {
    while(!Q.empty() ) {
        nod act=Q.front();
        int cst=dr[act.x][act.y][act.d];
        Q.pop_front();
            
        if(inborder(adv(act))) {
            nod next=adv(act);
            if(!viz[next.x][next.y][next.d]&&cst<dr[next.x][next.y][next.d]) {
                Q.push_front(next);
                dr[next.x][next.y][next.d]=cst;
            }
           
        }

        nod next=turnL(act);
        if(!viz[next.x][next.y][next.d]&&cst+1<dr[next.x][next.y][next.d]) {
            Q.push_back(next);
            dr[next.x][next.y][next.d]=cst+1;
        }
        
        next=turnR(act);
        if(!viz[next.x][next.y][next.d]&&cst+1<dr[next.x][next.y][next.d]) {
            Q.push_back(next);
            dr[next.x][next.y][next.d]=cst+1;
        }

        viz[act.x][act.y][act.d]=true;
    }
}


int main() {
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    
    scanf("%d%d",&N,&M);
    int xs,ys,xf,yf;
    scanf("%d%d%d%d",&xs,&ys,&xf,&yf);
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=M;j++) {
            scanf("%d",&x[i][j]);
        }
    }   

    initializare(xs,ys);
    dijkstra();

    int ans=INF;
    for(int i=0;i<8;i++) {
        ans=min(ans,dr[xf][yf][i]);
    }
    if(ans==INF) { 
        printf("-1");
    }
    else {
        printf("%d",ans);
    }

    return 0;
}