Cod sursa(job #862778)

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

void init()
{
    for (i=1;i<=8;i++)
    {
        for (j=1;j<=8;j++)
        {
            pac=i+j;
            if (pac>8)
                pac-=8;
            c++;
            if (c==5)
                c=1;
            cost[i][pac]=c;
        }
        cost[i][i]=0;
    }
}

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;
    while ((c<=cmax)&&(rez==-1))
    {
        while (!q[c].empty())
        {
            el=q[c].front();   q[c].pop();
            if (cmin[el.l][el.c][el.d]==c)
            {
                if ((el.l==l2)&&(el.c==c2))
                {   rez=c;   break;  }
                for (d=1;d<=8;d++)
                    if (!ma[el.l+vl[d]][el.c+vc[d]])
                    {
                        elac.l=el.l+vl[d];  elac.c=el.c+vc[d];  elac.d=d;
                        if (cmin[elac.l][elac.c][elac.d]>cmin[el.l][el.c][el.d]+cost[el.d][d])
                        {
                            cmin[elac.l][elac.c][elac.d]=cmin[el.l][el.c][el.d]+cost[el.d][d];
                            q[cmin[elac.l][elac.c][elac.d]].push(elac);
                        }
                        if (cmax<cmin[elac.l][elac.c][elac.d])
                            cmax=cmin[elac.l][elac.c][elac.d];

                    }
            }
        }
        c++;
    }
}

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