Cod sursa(job #49713)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 6 aprilie 2007 11:43:30
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <stdio.h>
#include <math.h>
#include <stack>
#define NMAX 505
#define INF 666000666
#define DMAX 8

using namespace std;

stack<int> L[3];
int N, M, A[NMAX][NMAX], D[NMAX][NMAX][DMAX+2], C, SL, SC, FL, FC;
int X[DMAX] = {1, 1, 0,-1,-1,-1, 0, 1}; //linie
int Y[DMAX] = {0, 1, 1, 1, 0,-1,-1,-1}; //coloana
int cost[DMAX+2][DMAX+2];

void expand(int nod)
{
        int i, j, dir, x, k;
        int ii, jj;

        dir = nod >> 18;
        j = (nod & 511);
        i = (nod >> 9) & 511;

        for (k = 0; k < DMAX; k++)
           if (cost[k][dir] < 3)
            if ((A[i+X[k]][j+Y[k]] == 0) && (D[i+X[k]][j+Y[k]][dir] > (C+cost[k][dir])))
            {
                ii = i+X[k];
                jj = j+Y[k];
                D[ii][jj][dir] = C+cost[k][dir];
                x = (ii << 9) + jj + (k << 18);
                L[ (C+cost[k][dir])%3 ].push(x);
            }
}

int main()
{
        int i, j, x = 0, k, min, d, t, nod;

        freopen("car.in", "r", stdin);
        scanf("%d %d", &N, &M);
        scanf("%d %d %d %d", &SL, &SC, &FL, &FC);

        for (i = 0; i < DMAX; i++)
            for (j = i+1; j < DMAX; j++)
            {
                x = j-i;
                if (x > 4) x = 8-x;
                cost[i][j] = cost[j][i] = x;
            }

        for (i = 0; i < NMAX; i++)
            for (j = 0; j < NMAX; j++) A[i][j] = 1;

        for (i = 0; i <= N; i++)
            for (j = 0; j <= M; j++)
                for (d = 0; d < DMAX; d++) D[i][j][d] = INF;

        for (d = 0; d < DMAX; d++) D[SL][SC][d] = 0;

        for (i = 1; i <= N; i++)
            for (j = 1; j <= M; j++) scanf("%d", &A[i][j]);

        for (i = 0; i < DMAX; i++)
                L[0].push((SL << 9) + SC + (i << 18));

        while ((L[0].size()+L[1].size()+L[2].size())>0)
        {
                t = C%3;
                while (L[t].size() > 0)
                {
                        nod = L[t].top();
                        L[t].pop();
                        expand(nod);
                }
                C++;
        }

        min = D[FL][FC][0];
        for (d = 0; d < DMAX; d++)
            if (min > D[FL][FC][d]) min = D[FL][FC][d];

        if (min == INF) min = -1;
        freopen("car.out", "w", stdout);
        printf("%d\n", min);

        return 0;
        
}