Cod sursa(job #1667397)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 28 martie 2016 21:42:18
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.61 kb
#include<iostream>
#include<fstream>
#include<queue>

using namespace std;

ifstream f("car.in");
ofstream g("car.out");

int A[505][505];
int Dist[505][505][9], Cost[9][9], Poz[505][505][9];
int Heap[2000005], Heap_Size;
int x[] = {-1, -1, -1, 0, 1, 1, 1, 0}, y[] = {-1, 0, 1, 1, 1, 0, -1, -1}, c[] = {3, 2, 1, 0, 1, 2, 3};
int n, m, xst, yst, xfi, yfi, sol;
int const oo = 1000000000;

void Read()
{
    int i, j;

    f>>n>>m>>xst>>yst>>xfi>>yfi;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            f>>A[i][j];
}


void Swap(int hx, int hy)
{
    int i, j, k, i1, j1, k1;

    k = Heap[hx] >> 18;
    j = (Heap[hx] & 511);
    i = (Heap[hx] >> 9) & 511;
    k1 = Heap[hy] >> 18;
    j1 = (Heap[hy] & 511);
    i1 = (Heap[hy] >> 9) & 511;

    swap(Heap[hx], Heap[hy]);
    swap(Poz[i][j][k], Poz[i1][j1][k1]);
}

void UpHeap(int nod)
{
    int tata, in, jn, kn, it, jt, kt;
    tata = nod/2;

    if(tata){

        kn = Heap[nod] >> 18;
        jn = (Heap[nod] & 511);
        in = (Heap[nod] >> 9) & 511;
        kt = Heap[tata] >> 18;
        jt = (Heap[tata] & 511);
        it = (Heap[tata] >> 9) & 511;

        if(Dist[it][jt][kt] > Dist[in][jn][kn]){
            Swap(tata, nod);
            UpHeap(tata);
        }
    }
}

void DownHeap(int nod)
{
    int son, jn, in, kn, is1, is2, js1, js2, ks1, ks2;

    son = 2*nod;

    if(son+1 <= Heap_Size){

        ks1 = Heap[son] >> 18;
        js1 = (Heap[son] & 511);
        is1 = (Heap[son] >> 9) & 511;
        ks2 = Heap[son+1] >> 18;
        js2 = (Heap[son+1] & 511);
        is2 = (Heap[son+1] >> 9) & 511;

        if(Dist[is1][js1][ks1] > Dist[is2][js2][ks2])
            son++;
    }

    if(son <= Heap_Size){

        kn = Heap[nod] >> 18;
        jn = (Heap[nod] & 511);
        in = (Heap[nod] >> 9) & 511;
        ks1 = Heap[son] >> 18;
        js1 = (Heap[son] & 511);
        is1 = (Heap[son] >> 9) & 511;

        if(Dist[is1][js1][ks1] < Dist[in][jn][kn]){
            Swap(nod, son);
            DownHeap(son);
        }
    }
}

void Precalc()
{
    int i, j, k;

    for(i=0; i<=7; i++){
        Cost[i][i] = 4;
        k = 0;
        for(j=i+1; j != i; j++, j%=8){
            Cost[i][j] = c[k++];
        }
    }

    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            for(k=0; k<8; k++){
                Dist[i][j][k] = oo;
                Heap[++Heap_Size] = (i << 9) + j + (k << 18);
                Poz[i][j][k] = Heap_Size;
            }

    for(i=0; i<=n+1; i++)
        A[i][0] = A[i][m+1] = 1;
    for(j=0; j<=m+1; j++)
        A[0][j] = A[n+1][j] = 1;
}

void Dijkstra()
{
    int i, j, k, ivec, jvec, cost, d, intrare, aux;

    for(i=0; i<8; i++){
        Dist[xst][yst][i] = 0;
        UpHeap(Poz[xst][yst][i]);
    }

    while(Heap_Size){
        aux = Heap[1];
        d = (aux >> 18);
        j = (aux & 511);
        i = (aux >> 9) & 511;
        Swap(1, Heap_Size);
        Heap_Size--;
        DownHeap(1);

        for(k=0; k<8; k++){
            ivec = i + x[k];
            jvec = j + y[k];
            cost = Cost[d][k];
            intrare = (k+4)%8;
            if(!A[ivec][jvec] && Dist[i][j][d] + cost < Dist[ivec][jvec][intrare]){
                Dist[ivec][jvec][intrare] = Dist[i][j][d] + cost;
                UpHeap(Poz[ivec][jvec][intrare]);
            }
        }
    }

    sol = oo;
    for(i=0; i<8; i++)
        sol = min(sol, Dist[xfi][yfi][i]);

    if(sol == oo)
        sol = -1;
    g<<sol<<"\n";
}

int main()
{
    Read();
    Precalc();
    Dijkstra();
    return 0;
}