Cod sursa(job #49873)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 6 aprilie 2007 15:17:34
Problema Car Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.28 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#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[DMAX+1][NMAX][NMAX], 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+1][DMAX+1];
char buf[350000];

int main()
{
        int i, j, x = 0, k, min, d, t, nod, dir, min1, min2;
        int ii, jj;

        FILE *f=fopen("car.in", "r");
        setbuffer(f,buf,sizeof(buf));
        fscanf(f,"%d %d", &N, &M);
        fscanf(f,"%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[d][i][j] = INF;

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

        for (i = 1; i <= N; i++)
            for (j = 1; j <= M; j++) fscanf(f,"%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();

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

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

        if (min1 == INF) min1 = -1;

        x = SL; SL = FL; FL = x;
        x = SC; SC = FC; FC = x;

        C = 0;
        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 <= N; i++)
            for (j = 0; j <= M; j++)
                for (d = 0; d < DMAX; d++) D[d][i][j] = INF;

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

        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();

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

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

        if (min2 == INF) min2 = -1;

        min = min1;
        if (min > min2) min = min2;

        freopen("car.out", "w", stdout);
        printf("%d\n", min);

        return 0;
        
}