Cod sursa(job #50329)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 7 aprilie 2007 14:46:05
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define NMAX 505
#define INF 666000666
#define DMAX 8

using namespace std;

int N, M, A[NMAX][NMAX], inQ[DMAX][NMAX][NMAX], C, SL, SC, FL, FC;
int X[DMAX] = {-1,-1, 0, 1, 1, 1, 0,-1};
int Y[DMAX] = { 0, 1, 1, 1, 0,-1,-1,-1};
char buf[350000];
int Q[2][NMAX*NMAX*DMAX];

int main()
{
        int i, j, min, found = 0, dir, s=0, d=1, slo=0, shi=0, dlo=0, dhi=-1, dir1;

        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 < NMAX; i++)
            for (j = 0; j < NMAX; j++) A[i][j] = 1;

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

        for (i = 0; i < DMAX; i++)
        {
                Q[0][shi++] = (SL << 9) + SC + (i << 18);
                inQ[i][SL][SC] = 1;
        }

        while (!found)
        {
                for (;slo<=shi;slo++)
                {
                        dir = Q[s][slo] >> 18;
                        j = (Q[s][slo] & 511);
                        i = (Q[s][slo] >> 9) & 511;

                        if (i == FL && j == FC) found = 1;
                
                        if ((A[i+X[dir]][j+Y[dir]]+inQ[dir][i+X[dir]][j+Y[dir]])==0)
                        {
                                inQ[dir][i+X[dir]][j+Y[dir]] = 1;
                                Q[s][shi++] = ((j+X[dir]) << 9) + (i+Y[dir]) + (dir << 18);
                        }
                }

                for (dlo=0;dlo<shi;dlo++)
                {
                        dir = Q[s][dlo] >> 18;
                        j = (Q[s][dlo] & 511);
                        i = (Q[s][dlo] >> 9) & 511;

                        dir1 = (dir+1)&7;
                        if ((A[i+X[dir1]][j+Y[dir1]]+inQ[dir1][i+X[dir1]][j+Y[dir1]])==0)
                        {
                                inQ[dir1][i+X[dir1]][j+Y[dir1]] = 1;
                                Q[d][dhi++] = ((j+X[dir1]) << 9) + (i+Y[dir1]) + (dir1 << 18);
                        }
                        dir1 = (dir-1+8)&7;
                        if ((A[i+X[dir1]][j+Y[dir1]]+inQ[dir1][i+X[dir1]][j+Y[dir1]])==0)
                        {
                                inQ[dir1][i+X[dir1]][j+Y[dir1]] = 1;
                                Q[d][dhi++] = ((j+X[dir1]) << 9) + (i+Y[dir1]) + (dir1 << 18);
                        }
                }
                        
                if (found == 0 && dhi == 0) C = -1, found = 1;

                C += (found==0);

                slo = 0; shi = dhi; dhi = 0;
                s = (s+1)&1; d = (d+1)&1;
        }

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

        return 0;
        
}