Cod sursa(job #132346)

Utilizator cos_minBondane Cosmin cos_min Data 5 februarie 2008 17:42:57
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <stdio.h>
#include <fstream>
using namespace std;

#define in "car.in"
#define out "car.out"
#define dim 501
#define infinit (1<<29)

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

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

inline int abs(int A)
{
       if ( A < 0 ) return (-1)*A;
       return A;
}

// N, NV, V, SV, S, SE, E, NE

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 = 1; j <= M; j++ )
            for ( int k = 0; k < 9; k++ )
                C[i][j][k] = infinit, Sel[i][j][k] = 0;
    
    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 - 1 ) * M + ( yS - 1 ) * 8 + i;
        act = i+1;
        Sel[xS][yS][i] = 1;
    }
    
    if ( A[xS][yS] || A[xF][yF] )
    {
         printf("-1\n");
         
         return 0;
    }
    
    while ( act > 0 ) 
    {
          for ( int s = 1; s <= act; s++ )
          {
              int t = Q1[s];
              
              dir = t % 8, dir /= 8;
              y = ( t % M ) + 1;
              x = ( t / M ) + 1;
              
              for ( int d = 0; d < 8; d++ )
              {
                  xnou = x+di[d], ynou = y+dj[d];
                  
                  if ( Ok(xnou,ynou) && abs(dir-d) <= 2 )
                     if ( C[xnou][ynou][d] > C[x][y][dir] + abs(dir-d) )
                     {
                          C[xnou][ynou][d] = C[x][y][dir] + abs(dir-d);
                          last++;
                          Q2[last] = ( xnou - 1 ) * M + ( ynou - 1 ) * 8 + d;
                     }
              }
          }
          
          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;
}