Cod sursa(job #1814629)

Utilizator silkMarin Dragos silk Data 24 noiembrie 2016 11:56:56
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <cstdio>
#include <vector>
#define INF 1<<30
#define VMax 1000000
#define NMax 502
#define DMax 8
#define DIM 10000
#define ushort unsigned short
#define ABS(x)((x)>0?(x):(-(x)))
using namespace std;
char buff[DIM];
int poz;

struct car
{
    ushort x,y;
    char k0,k1;
};

vector<car>v[VMax+1];
int deja[NMax+1][NMax+1][DMax+1];
char cost[DMax+1][DMax+1];
char a[NMax+1][NMax+1];

char dirx[8]={-1,-1,0,1,1,1,0,-1};
char diry[8]={0,1,1,1,0,-1,-1,-1};

void Precalc()
{
    int i,j,x;

    for(i = 0; i < 8; ++i)
        for(x = 0; x < 5; ++x)
        {
            j = i+x;
            if( j > 7 ) j -= 8;
            cost[i][j] = x;

            j = i-x;
            if( j < 0 ) j += 8;
            cost[i][j] = x;
        }
}

void Read(char& numar)
{
    numar = 0;
    while(buff[poz]<'0'||buff[poz]>'9')
    if(++poz==DIM) fread(buff,1,DIM,stdin),poz=0;
    while(buff[poz]>='0'&&buff[poz]<='9')
    {
        numar = numar*10 + buff[poz] - '0';
        if(++poz==DIM) fread(buff,1,DIM,stdin),poz=0;
    }
}

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

    int count=0,ans,i,j,k,N,M,x0,y0,xf,yf,x,y,xc,yc,k0,k1,sum;
    car temp;

    scanf("%d %d",&N,&M);
    scanf("%d %d %d %d",&x0,&y0,&xf,&yf);

    Precalc();

    int f[2];
    f[0] = INF;
    f[1] = -INF;

    for(i = 1; i <= N; ++i)
        for(j = 1; j <= M; ++j)
        {
            Read(a[i][j]);
            for(k = 0; k < 8; ++k) deja[i][j][k] = f[ a[i][j] ];
        }

    for(k = 0; k < 8; ++k) deja[x0][y0][k] = 0;
    temp.x = x0;
    temp.y = y0;

    for(k = 0; k < 8; ++k)
    if( deja[ x0+dirx[k] ][ y0+diry[k] ][k] == INF )
    {
        temp.k1 = temp.k0 = k;
        deja[ x0+dirx[k] ][ y0+diry[k] ][k] = 0;
        v[0].push_back(temp);
    }

    for(i = 0; i < VMax; ++i)
    {
        while( !v[i].empty() )
        {
            ++count;
            temp = v[i].back();
            v[i].pop_back();

            x = temp.x;
            y = temp.y;
            k0 = temp.k0;
            k1 = temp.k1;

            if( deja[ x+dirx[k1] ][ y+diry[k1] ][k1] == i )
            {
                xc = x+dirx[k1];
                yc = y+diry[k1];
                for(k = 0; k < 8; ++k)
                {
                    sum = deja[xc][yc][k1] + cost[k1][k];
                    if( sum < deja[ xc+dirx[k] ][ yc+diry[k] ][k] && cost[k1][k] <= 2 )
                    {
                        deja[ xc+dirx[k] ][ yc+diry[k] ][k] = sum;
                        temp.x = xc;
                        temp.y = yc;
                        temp.k0 = k1;
                        temp.k1 = k;
                        v[sum].push_back(temp);
                    }
                }
            }
        }
    }

    for(ans = INF, k = 0; k < 8; ++k)
    if( deja[xf][yf][k] < ans ) ans = deja[xf][yf][k];

    if(ans==INF || ans==-INF) printf("-1\n");
    else printf("%d",ans);



return 0;
}