Cod sursa(job #205714)

Utilizator savimSerban Andrei Stan savim Data 2 septembrie 2008 18:40:21
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define maxl 510
#define maxval 500010

int n,m,i,j,k,l,p,q,dir,newX,newY;
int a[maxl][maxl];
int x[5],y[5];
int d1[8]={0,-1,-1,-1,0,1,1,1};
int d2[8]={1,1,0,-1,-1,-1,0,1};
int cost[8][8];
int val[maxl][maxl][8];
vector <int> c[maxval];

void expand()
{
    for (j=0; j<8; j++)
    {
        newX=p+d1[j];newY=q+d2[j];
        if (p==2 && q==2 && j==5)
        {
            i++;i--;
        }
        if (!a[newX][newY] &&
            (val[newX][newY][j]<0 || val[p][q][dir]+cost[dir][j]<val[newX][newY][j]))
        {
            val[newX][newY][j]=val[p][q][dir]+cost[j][dir];
            c[i+cost[j][dir]].push_back(((newX-1)*m+(newY-1))*8+j);
        }
    }
}

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

    scanf("%d %d",&n,&m);
    scanf("%d %d %d %d",&x[1],&y[1],&x[2],&y[2]);

    for (i=0; i<=n+1; i++)
        for (j=0; j<=m+1; j++)
            a[i][j]=1;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            scanf("%d",&a[i][j]);
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            for (k=0; k<8; k++) val[i][j][k]=-1;

    for (i=0; i<8; i++)
        for (j=0; j<i; j++)
        {
            k=i-j;
            if (k>4) k=cost[i-1][j]-1;
            cost[i][j]=k;
            cost[8-i-1][8-j-1]=k;
        }
        
    for (i=0; i<=7; i++)
    {
        c[0].push_back(((x[1]-1)*m+y[1]-1)*8+i);
        val[x[1]][y[1]][i]=0;
    }
    
    for (i=0; i<=maxval; i++)
        while (c[i].size()>0)
        {
            if (i==2)
            {
            i++;i--;
            }
            
            l=c[i].size()-1;
            k=c[i][l];
            c[i].pop_back();
            
            dir=k%8;k/=8;
            q=(k%m)+1;
            p=(k/m)+1;
            if (p==x[2] && q==y[2])
            {
                printf("%d\n",i);
                return 0;
            }

            expand();
        }

    printf("-1\n");
    return 0;
}