Cod sursa(job #2121166)

Utilizator stefanchistefan chiper stefanchi Data 3 februarie 2018 13:29:15
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <cstdio>
#include <queue>
#define MAX 505
using namespace std;
int n,m;
int xstart,ystart,xfinal,yfinal;
int drum[MAX][MAX],cost[MAX][MAX];
int xdir[8]= {-1,-1,0,1,1,1,0,-1};
int ydir[8]= {0,1,1,1,0,-1,-1,-1};
int costdir[8]= {1,1,1,1,1,1,1,1};

struct nod
{
    int x,y,directie;
    nod()
    {
        x = 0;
        y = 0;
        directie = -1;
    }
};

void bordare()
{
    for(int i = 0 ; i <= n + 1; i++)
    {
        drum[i][0] = 1;
        drum[i][m+1] = 1;
    }
    for(int i = 0 ; i <= m+1 ; i++)
    {
        drum[0][i] = 1;
        drum[n+1][i] = 1;
    }
}

void updatecost(int directie)
{
    if(directie == -1)
        return;
    costdir[directie]=0;
    int stanga = directie,dreapta=directie;
    int contor= 1;
    while(contor <= 4)
    {
        if(stanga - contor < 0 )
            stanga = 7 + stanga - contor + 1;
        else
            stanga -=contor;
        if(dreapta + contor > 7)
            dreapta = 0 + dreapta - contor - 1;
        else
            dreapta +=contor;
        costdir[stanga] = contor;
        costdir[dreapta]= contor;
        contor++;
        stanga = directie;
        dreapta = directie;
    }

}


void lee()
{
    nod element,vecin;
    queue<nod> coada;
    element.x = xstart;
    element.y = ystart;
    element.directie = -1;
    coada.push(element);
    while(!coada.empty())
    {
        element = coada.front();
        coada.pop();
        updatecost(element.directie);
        for(int k = 0 ; k < 8 ; k++)
        {
            vecin.x = element.x + xdir[k];
            vecin.y = element.y + ydir[k];
            vecin.directie = k;
            if(drum[vecin.x][vecin.y] == 0)
            {
                if(cost[vecin.x][vecin.y] == 0)
                {
                    cost[vecin.x][vecin.y] = cost[element.x][element.y]+costdir[k];
                    coada.push(vecin);
                }
                else
                {
                    if(cost[vecin.x][vecin.y] > cost[element.x][element.y] + costdir[k])
                    {
                        cost[vecin.x][vecin.y] = cost[element.x][element.y]+costdir[k];
                        coada.push(vecin);
                    }
                }
            }
        }
    }
}



void read()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    scanf("%d %d\n%d %d %d %d",&n,&m,&xstart,&ystart,&xfinal,&yfinal);
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
            scanf("%d ",&drum[i][j]);
    }
    drum[xstart][ystart] = 1;
    bordare();
}

int main()
{
    read();
    int ok = 0;
    for(int k = 0 ; k < 7 && ok == 0; k++)
        if(drum[xfinal+xdir[k]][yfinal+ydir[k]] == 0)
            ok = 1;
    if(ok == 0)
        printf("-1");
    else
    {
        lee();
        printf("%d",cost[xfinal][yfinal]);
    }
    return 0;
}