Cod sursa(job #1666786)

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

using namespace std;

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

struct triplet{
    int i, j, d;
};

bool A[505][505];
int Dist[505][505][9], Cost[9][9];
queue <triplet> Q;
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 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<=7; k++)
                Dist[i][j][k] = oo;
}

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

    tri.i = xst;
    tri.j = yst;
    tri.d = 8;
    Q.push(tri);

    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;

    while(Q.size()){
        i = Q.front().i;
        j = Q.front().j;
        d = Q.front().d;
        Q.pop();

        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;
                aux.i = ivec;
                aux.j = jvec;
                aux.d = intrare;
                Q.push(aux);
            }
        }
    }

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

    g<<sol<<"\n";
}

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