Cod sursa(job #1667428)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 28 martie 2016 22:06:27
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include<iostream>
#include<fstream>
#include<list>
#include<iterator>

using namespace std;

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

int A[505][505];
int Dist[505][505][8], Cost[9][9];
list <int>::iterator Poz[505][505][8];
list <int> L[100005];
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 = 100000;

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 Precalc()
{
    int i, j, k;
    list <int>::iterator t;

    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;
                L[oo].push_back((i << 9) + j + (k << 18));
                t = L[oo].end();
                t--;
                Poz[i][j][k] = t;
            }

    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, l;
    list <int>::iterator t, it;

    for(i=0; i<8; i++){
        Dist[xst][yst][i] = 0;
        L[oo].erase(Poz[xst][yst][i]);
        L[0].push_back((xst << 9) + yst + (i << 18));
        t = L[0].end(); t--;
        Poz[xst][yst][i] = t;
    }

    for(l=0; l<=oo; l++)
        for(it = L[l].begin(); it != L[l].end(); it++){
            d = (*it >> 18);
            j = (*it & 511);
            i = (*it >> 9) & 511;

            if(i==xfi && j==yfi)
                return;

            for(k=0; k<8; k++){
                ivec = i + x[k];
                jvec = j + y[k];
                cost = Cost[d][k];
                intrare = k+4;
                if(intrare > 7)
                    intrare -= 8;
                if(!A[ivec][jvec] && l + cost < Dist[ivec][jvec][intrare]){
                    L[Dist[ivec][jvec][intrare]].erase(Poz[ivec][jvec][intrare]);
                    Dist[ivec][jvec][intrare] = l + cost;
                    L[Dist[ivec][jvec][intrare]].push_back((ivec << 9) + jvec + (intrare << 18));
                    t = L[Dist[ivec][jvec][intrare]].end(); t--;
                    Poz[ivec][jvec][intrare] = t;
                }
            }
        }
}

int main()
{
    Read();
    Precalc();
    Dijkstra();

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

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

    return 0;
}