Cod sursa(job #2174646)

Utilizator tqmiSzasz Tamas tqmi Data 16 martie 2018 12:51:18
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <iostream>
#include <fstream>
#define oo 1<<30
#define Nmax 505
using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");

struct nod{
    int x,y;
};
nod heap[Nmax*Nmax];
nod S,F;
int Ux[] = {0,1,1,1,0,-1,-1,-1};
int Uy[] = {1,1,0,-1,-1,-1,0,1};

int A[Nmax][Nmax],C[Nmax][Nmax],D[Nmax][Nmax];
int Nheap,N,M;

void upheap(int node){
    int tata = node/2;
    if(node==1)
        return;
    if(C[heap[node].x][heap[node].y]<=C[heap[tata].x][heap[tata].y]){
        swap(heap[node],heap[tata]);
        upheap(tata);
    }
}

void downheap(int node){
    int son1 = node*2;
    int son2 = son1+1;

    if(son1 > Nheap)
        return;

    if(son1 == Nheap){
        if(C[heap[son1].x][heap[son1].y]<=C[heap[node].x][heap[node].y]){
            swap(heap[son1],heap[node]);
            downheap(son1);
        }
        return;
    }
    if(son1<Nheap){
        if(C[heap[son1].x][heap[son1].y]<=C[heap[son2].x][heap[son2].y]){
            if(C[heap[son1].x][heap[son1].y]<=C[heap[node].x][heap[node].y]){
                swap(heap[son1],heap[node]);
                downheap(son1);
            }
            return;
        }else{
            if(C[heap[son2].x][heap[son2].y]<=C[heap[node].x][heap[node].y]){
                swap(heap[son2],heap[node]);
                downheap(son2);
            }
            return;
        }
    }
}

int abs(int x){
    if(x<0)
        return -x;
    return x;
}

int main()
{
    fin>>N>>M;
    fin>>S.x>>S.y>>F.x>>F.y;
    for(int i=1 ;i<=N;i++){
        for(int j=1;j<=M;j++){
            fin>>A[i][j];
            C[i][j] =oo;
        }
    }
    for(int i=0;i<=N+1;i++){
        A[i][0] = A[i][M+1] = 1;
    }
    for(int i=0;i<=M+1;i++){
        A[0][i] = A[N+1][i] = 1;
    }
    C[S.x][S.y] = 0;

    for(int i=0;i<8;i++){
        nod nn;
        nn.x = S.x+Ux[i];
        nn.y = S.y+Uy[i];
        int c = 0;
        if(C[S.x][S.y]+c<C[nn.x][nn.y]){
            C[nn.x][nn.y] = C[S.x][S.y]+c;
            D[nn.x][nn.y] = i;
            Nheap++;
            heap[Nheap] = nn;
            upheap(Nheap);
        }
    }
    while(Nheap){
        nod cur = heap[1];
        swap(heap[1],heap[Nheap]);
        Nheap--;
        downheap(1);
        if(A[cur.x][cur.y] == 1)
            continue;
        A[cur.x][cur.y] = 1;
        nod nn;
        for(int i=0;i<8;i++){
            nn.x = cur.x+Ux[i];
            nn.y = cur.y+Uy[i];
            if(A[nn.x][nn.y]==1)
                continue;
            int c = min(abs(i-D[cur.x][cur.y]),8-abs(i-D[cur.x][cur.y]));
            if(C[cur.x][cur.y]+c<C[nn.x][nn.y]){
                C[nn.x][nn.y] = C[cur.x][cur.y]+c;
                D[nn.x][nn.y] = i;
                Nheap++;
                heap[Nheap] = nn;
                upheap(Nheap);
            }
        }
    }
    fout<<C[F.x][F.y];
    return 0;
}