Cod sursa(job #863031)

Utilizator lianaliana tucar liana Data 23 ianuarie 2013 10:38:14
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include<stdio.h>
#include<queue>
using namespace std;
#define nmax 505
#define mmax 505
#define dmax 9
#define inf nmax*nmax*dmax
struct element{long l, c, d;};
long l1, c1, l2, c2, i, n, m, c, cmax, j, pac, d, rez, ad, ac, urm;
bool ma[nmax][nmax];
long cmin[nmax][mmax][dmax];
queue <element> q[3];
element el, elac;
long vl[10]={0,-1,-1,-1,0,1,1,1,0,-1};
long vc[10]={-1,-1,0,1,1,1,0,-1,-1,-1};

void citire()
{
    scanf("%ld %ld",&n,&m);
    scanf("%ld %ld %ld %ld",&l1,&c1,&l2,&c2);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
        {
            scanf("%ld",&ma[i][j]);
            for (d=1;d<=8;d++)
                cmin[i][j][d]=inf;
        }

    for (i=0;i<=n+1;i++)
        ma[i][0]=ma[i][m+1]=1;
    for (j=0;j<=m+1;j++)
        ma[0][j]=ma[n+1][j]=1;

    for (d=1;d<=8;d++)
    {
        el.l=l1;    el.c=c1;    el.d=d;
        q[0].push(el);
        cmin[l1][c1][d]=0;
    }
}

void rezolvare()
{
    c=0;    ac=0;   urm=1;
    while ((c<=cmax)&&(rez==-1))
    {
        while (!q[ac].empty())
        {
            el=q[ac].front();   q[ac].pop();
            if (cmin[el.l][el.c][el.d]==c)
            {
                if ((el.l==l2)&&(el.c==c2))
                {   rez=c;   break;  }
                for (ad=-1;ad<=1;ad++)
                {
                    if (ad*ad==1)
                    {
                        elac=el;
                        elac.d=(el.d+ad+8)%8;
                        if (elac.d==0)
                            elac.d=8;
                    }
                    else
                    { elac.l=el.l+vl[el.d];  elac.c=el.c+vc[el.d];  elac.d=el.d;}
                    if (!ma[elac.l][elac.c])
                    {
                        if (cmin[elac.l][elac.c][elac.d]>cmin[el.l][el.c][el.d]+ad*ad)
                        {
                            cmin[elac.l][elac.c][elac.d]=cmin[el.l][el.c][el.d]+ad*ad;
                            if  (cmin[elac.l][elac.c][elac.d]==c )
                                q[ac].push(elac);
                            else
                                q[urm].push(elac);
                        }
                        if (cmax<cmin[elac.l][elac.c][elac.d])
                            cmax=cmin[elac.l][elac.c][elac.d];
                    }
                }
            }
        }
        c++;    ac=1-ac;    urm=1-urm;
    }
}

int main()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    citire();
    rez=-1;
    rezolvare();
    printf("%ld",rez);
    return 0;
}