Cod sursa(job #132943)

Utilizator cos_minBondane Cosmin cos_min Data 6 februarie 2008 22:58:05
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <stdio.h>
#include <fstream>
using namespace std;

#define in "car.in"
#define out "car.out"
#define dim 501
#define infinit (1<<20)
#define dir2 H[dir][d]
#define size (1<<19)

int N, M;
int xS, yS, xF, yF;
int C[dim][dim][9], H[9][9], D[9]; // costul minim de a ajunge in punctul (i,j) folosind ultima directie k
int Q1[size], Q2[size];
bool A[dim][dim];

int di[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dj[] = { 0, -1, -1, -1, 0, 1, 1, 1 };

bool Ok(int,int);

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d", &N, &M);
    scanf("%d%d%d%d", &xS, &yS, &xF, &yF);
    for ( int i = 1; i <= N; i++ )
        for ( int j = 1; j <= M; j++ )
            scanf("%d", &A[i][j]);
    
    for ( int i = 1; i <= N; i++ )
        for ( int j = i; j <= M; j++ )
            for ( int k = 0; k < 8; k++ )
                C[i][j][k] = C[j][i][k] = infinit;
    
    int x, y, dir;
    int xnou, ynou;
    int act, last = 0; 
    
    for ( int i = 0; i < 8; i++ ) 
    {
        C[xS][yS][i] = 0;
        Q1[i+1] = (xS<<9) + yS + (i<<18);
    }
    
    D[0] = 2, D[1] = 1, D[2] = 0, D[3] = 1, D[4] = 2;
    
    for ( int i = 0; i < 8; i++ )
    {
        for ( int j = i-2, k = 0; j <= i+2; j++, k++ )
        {
            if ( j < 0 ) H[i][k] = 8 + j;
            else if ( j >= 8 ) H[i][k] = j % 8;
            else H[i][k] = j;
        }
    }
    
    act = 8;
    
    if ( A[xS][yS] || A[xF][yF] )
    {
         printf("-1\n");
         
         return 0;
    }
    
    while ( act ) 
    {
          for ( int s = 1; s <= act; ++s )
          {
              dir = (Q1[s]>>18);
              y = (Q1[s]&511);
              x = ((Q1[s]>>9)&511);
              
              for ( int d = 0; d <= 4; ++d )
              {
                  xnou = x+di[dir2], ynou = y+dj[dir2];
                  
                  if ( Ok(xnou,ynou) )
                     if ( C[xnou][ynou][dir2] > C[x][y][dir] + D[d] )
                     {
                          C[xnou][ynou][dir2] = C[x][y][dir] + D[d];
                          ++last;
                          Q2[last] = (xnou<<9) + ynou + (dir2<<18);;
                     }
              }
          }
          
          act = last, last = 0;
          for ( int s = 1; s <= act; s++ ) Q1[s] = Q2[s];
    }
    
    int minim = infinit;
    
    for ( int i = 0; i < 8; i++ )
        if ( minim > C[xF][yF][i] ) minim = C[xF][yF][i];
    
    if ( minim == infinit ) printf("-1\n");
    else                    printf("%d\n", minim);
}

bool Ok(int i, int j)
{
     if ( i < 1 || i > N || j < 1 || j > M ) return 0;
     if ( A[i][j] ) return 0;
     return 1;
}