Cod sursa(job #50344)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 7 aprilie 2007 15:06:02
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <cstdio>
#include <cstring>
#define NMAX 505
#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, found = 0, dir, s=0, d=1, slo, shi=-1, dlo, 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] = (SC << 9) + SL + (i << 18);
                inQ[i][SL][SC] = 1;
        }

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

                        if (i == FL && j == FC) found = 1;
                        else
                           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+Y[dir]) << 9) + (i+X[dir]) + (dir << 18);
                           }
                }

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

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

                C += (found==0);

                shi = dhi; dhi = -1;
                s = (s+1)&1; d = (d+1)&1;
                memset(Q[d],0,sizeof(Q[d]));
        }

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

        return 0;
        
}