Cod sursa(job #1305516)

Utilizator OctaDuiu Octavian Octa Data 29 decembrie 2014 20:37:29
Problema Car Scor 40
Compilator cpp Status done
Runda tema_vacanta_iarna Marime 1.76 kb
#include<cstdio>
#include<queue>
#include<algorithm>
#define inf 999999999
using namespace std;
int dx[]={1, 1, 0, -1, -1, -1, 0, 1};
int dy[]={0, 1, 1,  1,  0, -1,-1,-1};

struct element
{
    int x,y,direction;
}E;

queue < element > q;

int i,j,n,m,x,y,X,Y;
bool A[103][103];
int p[103][103][8];

int main ()
{
    freopen("car.in","r",stdin);freopen("car.out","w",stdout);

    scanf("%d %d",&n,&m);
    scanf("%d %d",&x,&y);
    scanf("%d %d",&X,&Y);

    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            scanf("%d",&A[i][j]),A[i][j]=1-A[i][j];


    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            for(int k=0;k<8;++k)
                p[i][j][k]=inf;

    for(i=0;i<8;++i)
    {
        E.x=x; E.y=y; E.direction=i;
        q.push(E);
        p[x][y][i]=0;
    }

    while(!q.empty() )
    {
        E=q.front(); q.pop();

        int la,ca,lv,cv,d,di;

        lv=E.x+dx[E.direction]; cv=E.y+dy[E.direction];
        la=E.x; ca=E.y;
        d=E.direction; di=E.direction;

        if(A[lv][cv] && p[lv][cv][d]>p[la][ca][d])
        {
            p[lv][cv][d]=p[la][ca][d];
            E.x=lv; E.y=cv; E.direction=d;
            q.push(E);
        }

        d=(di+7)%8;
        if(p[la][ca][di]+1<p[la][ca][d])
        {
            p[la][ca][d]=p[la][ca][di]+1;
            E.x=la; E.y=ca; E.direction=d;
            q.push(E);
        }

        d=(di+9)%8;
        if(p[la][ca][di]+1<p[la][ca][d])
        {
            p[la][ca][d]=p[la][ca][di]+1;
            E.x=la; E.y=ca; E.direction=d;
            q.push(E);
        }
    }

    int Min=inf;
    for(i=0;i<8;++i)
        Min=min(Min,p[X][Y][i]);

    if(Min==inf)  printf("-1\n");
        else      printf("%d\n",Min);

 return 0;
}