Cod sursa(job #1255327)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 4 noiembrie 2014 18:10:07
Problema Car Scor 60
Compilator cpp Status done
Runda aaaaaaaaaaaaaaaaaaaaaa Marime 1.95 kb
#include <stdio.h>
#include <queue>
#define NMax 505
using namespace std;
 
const char IN[]="car.in",OUT[]="car.out";
const int d[8][2]={ {-1,-1} , {-1,0} , {-1,1} , {0,1} , {1,1} , {1,0} , {1,-1} , {0,-1}};
 
int N,M;
bool a[NMax][NMax];
int T[NMax][NMax][8];
struct point
{ int x,y;} start,finish;
struct poz
{ int x,y,d;};
 
int abs(int x)
{
    return (x<0) ? -x : x;
}
 
int Lee(point start , point finish)
{
    int i;
    queue<poz> qu;
    poz x;
     
    x.x=start.x;x.y=start.y; x.d=0;
    for (i=0;i<8;i++) T[x.x][x.y][i]=1;
    for (i=0;i<8;i++)
    {
        poz tmp={x.x+d[i][0],x.y+d[i][1],i};
        if ( !a[tmp.x][tmp.y] )
        {
            qu.push(tmp);
            T[tmp.x][tmp.y][i]=1;
        }
    }
    while (!qu.empty())
    {
        x=qu.front();
        qu.pop();
        for (i=0;i<8;i++)
        {
            poz tmp={x.x+d[i][0],x.y+d[i][1],i};
            if ( ! a[tmp.x][tmp.y] && abs(i-x.d)<3 && (!T[tmp.x][tmp.y][i] || T[tmp.x][tmp.y][i]>T[x.x][x.y][x.d]+abs(i-x.d)))
            {
                qu.push(tmp);
                T[tmp.x][tmp.y][i]=T[x.x][x.y][x.d]+abs(i-x.d);
            }
        }
    }
    int min=-1;
    for (i=0;i<8;i++)
        if ( (min<0 || T[finish.x][finish.y][i]<min) && T[finish.x][finish.y][i])
            min=T[finish.x][finish.y][i];
    return (min>0) ? min-1 : min;
}
 
int main()
{
    int i,j,x;
    freopen(IN,"r",stdin);
    scanf("%d%d%d%d%d%d",&N,&M,&start.x,&start.y,&finish.x,&finish.y);
    for (i=0;i<=M+1;i++) a[0][i]=a[N+1][i]=1;
    for (i=1;i<=N;i++){
        a[i][0]=a[i][N+1]=1;
        for (j=1;j<=M;j++)
            scanf("%d",&x),
            a[i][j]= x!=0 ;
    }
    fclose(stdin);
    /*for (i=0;i<=N+1;i++){
        for (j=0;j<=M+1;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }*/
     
    freopen(OUT,"w",stdout);
    printf("%d\n",Lee(start,finish));
    fclose(stdout);
    return 0;
}