Cod sursa(job #132339)

Utilizator cos_minBondane Cosmin cos_min Data 5 februarie 2008 17:31:11
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.13 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[3][dim*dim*8], Q2[3][dim*dim*8];
bool A[dim][dim];

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

void BuildH();

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;
    
    int x, y, dir;
    int xnou, ynou;
    int act, last = 0; 
    
    for ( int i = 0; i < 8; i++ ) 
    {
        C[xS][yS][i] = 0;
        Q1[0][i+1] = xS, Q1[1][i+1] = yS, Q1[2][i+1] = i;
        act = i+1;
    }
    
    if ( A[xS][yS] || A[xF][yF] )
    {
         printf("-1\n");
         
         return 0;
    }
    
    while ( act > 0 ) 
    {
          for ( int s = 1; s <= act; s++ )
          {
              x = Q1[0][s], y = Q1[1][s], dir = Q1[2][s];
              
              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[0][last] = xnou, Q2[1][last] = ynou, Q2[2][last] = d;
                     }
              }
          }
          
          act = last, last = 0;
          for ( int s = 1; s <= act; s++ )
              Q1[0][s] = Q2[0][s], Q1[1][s] = Q2[1][s], Q1[2][s] = Q2[2][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;
}

/*void BuildH()
{
     for ( int i = 0; i <= 8; i++ )
         for ( int j= 0; j <= 8; j++ )
             H[i][j] = infinit;
     
     for ( int i = 0; i < 8; i++ ) H[i][i] = 0;
     
     H[0][1] = 1, H[0][2] = 2, H[0][6] = 2, H[0][7] = 1;
     H[1][0] = 1, H[1][2] = 1, H[1][3] = 2, H[0][7] = 2;
     H[2][0] = 2, H[2][1] = 1, H[2][3] = 1, H[2][4] = 2;
     H[3][1] = 2, H[3][2] = 1, H[3][4] = 1, H[3][5] = 2;
     H[4][2] = 2, H[4][3] = 1, H[4][5] = 1, H[4][6] = 2;
     H[5][3] = 2, H[5][4] = 1, H[5][6] = 1, H[5][7] = 2;
     H[6][4] = 2, H[6][5] = 1, H[
     
}*/