Cod sursa(job #2629791)

Utilizator AokijiAlex M Aokiji Data 22 iunie 2020 17:34:26
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.83 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

ifstream f ("car.in");
ofstream g ("car.out");

int n,m;
int startx, starty, stopx, stopy;
int mak[501][501];
int cost[501][501][4][4];
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

struct Dir
{
    int dirx;
    int diry;
};
struct Nod
{
    int x;
    int y;
    Dir commingdir;
    int val;
};

//queue < Nod> coada;

Nod heap[500004];
int nn;

Nod getMin()
{
    return heap[1];
}

void add(Nod x)
{
    nn++;
    int poz=nn;
    heap[nn]=x;
    while(poz>1 && heap[poz/2].val>heap[poz].val)
    {
        swap(heap[poz/2], heap[poz]);
        poz/=2;
    }
}

int popMin()
{
    heap[1]=heap[nn];
    heap[nn]={0,0,{0,0},0};
    int poz=1;
    nn--;
    while(2*poz<=nn)
    {
        poz*=2;
        if(poz<nn && heap[poz].val>heap[poz+1].val) poz++;
        if(heap[poz].val < heap[poz/2].val)
            swap(heap[poz/2], heap[poz]);
        else poz=nn;
    }
}

bool isok(int x, int y)
{
    if(1<=x && x<=n && 1<=y && y<=m)
        return true;
    return false;
}

void lee()
{
   //coada.push({startx,starty,{0, 0}});
    add({startx,starty,{0, 0}});
    Nod elem={startx, starty};
    int inext, jnext;
    while(nn>0)
    {
        elem=getMin();

        int icurent = elem.x;
        int jcurent = elem.y;
        Dir dirr=elem.commingdir;
        popMin();
        Nod child;
        Dir d;
        if(dirr.dirx==0 && dirr.diry==0)
        {
            for(int dd=0;dd<8;++dd)
            {
                inext=icurent+dx[dd];
                jnext=jcurent+dy[dd];
                if(isok(inext, jnext))
                {
                    if(icurent==startx && jcurent==starty && mak[inext][jnext]==0)
                    {
                       // mak[inext][jnext]=mak[icurent][jcurent];
                        child.x=inext;
                        child.y=jnext;
                        d.dirx=inext-startx;
                        d.diry=-(jnext-starty);
                        child.commingdir=d;
                        cost[inext][jnext][d.dirx+1][d.diry+1]=0;
                        child.val=0;
                        add(child);
                    }
                }
            }
        }
        else
        {
            for(int dd=0;dd<8;++dd)
            {
                inext=icurent+dx[dd];
                jnext=jcurent+dy[dd];
                if(isok(inext, jnext) && mak[inext][jnext]==0)
                {
                    //cout<<"k";
                    child.x=inext;
                    child.y=jnext;
                    d.dirx=inext-icurent;
                    d.diry=-(jnext-jcurent);
                    Dir cdir;
                    cdir.dirx=2*(d.dirx*dirr.dirx+d.diry*dirr.diry)/(dirr.dirx*dirr.dirx+dirr.diry*dirr.diry);
                    cdir.diry=2*(d.diry*dirr.dirx - d.dirx*dirr.diry)/(dirr.dirx*dirr.dirx+dirr.diry*dirr.diry);
                    if(abs(cdir.dirx)==2 )
                    {
                        cdir.dirx/=2;
                        cdir.diry/=2;
                    }
                    else
                        if(abs(cdir.diry)==2 )
                        {
                            cdir.dirx/=2;
                            cdir.diry/=2;
                        }
                    child.commingdir=d;
                    if(cdir.dirx==1&& cdir.diry==0 && (cost[inext][jnext][d.dirx+1][d.diry+1]>cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]) )
                            cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1] , child.val=0, add(child) ;
                    else
                        if(cdir.dirx==1&& abs(cdir.diry)==1 && (cost[inext][jnext][d.dirx+1][d.diry+1]>cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+1 ))
                            cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+1 , child.val=1, add(child);
                        else
                            if(cdir.dirx==0&& abs(cdir.diry)==1 && (cost[inext][jnext][d.dirx+1][d.diry+1]>cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+2))
                                cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+2 , child.val=2, add(child);
                }
            }
        }
    }
}

int main()
{
    f>>n>>m>>startx>>starty>>stopx>>stopy;
    //  if(mak[startx][starty]==-1)
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            cost[i][j][0][0]=1e9;
            cost[i][j][0][1]=1e9;
            cost[i][j][0][2]=1e9;
            cost[i][j][1][0]=1e9;
            cost[i][j][1][1]=1e9;
            cost[i][j][1][2]=1e9;
            cost[i][j][2][0]=1e9;
            cost[i][j][2][1]=1e9;
            cost[i][j][2][2]=1e9;
            f>>mak[i][j];

        }
    }
    if(mak[startx][starty]==1 || mak[stopx][stopy] == 1)
    {
        g<<"-1";
        return 0;
    }
    cost[startx][starty][0][0]=0;
    cost[startx][starty][0][1]=0;
    cost[startx][starty][0][2]=0;
    cost[startx][starty][1][0]=0;
    cost[startx][starty][1][1]=0;
    cost[startx][starty][1][2]=0;
    cost[startx][starty][2][0]=0;
    cost[startx][starty][2][1]=0;
    cost[startx][starty][2][2]=0;
    lee();
    int mi=1e9;
    for(int di=0;di<3;++di)
    {
        for(int dj=0;dj<3;++dj)
        {
            //g<<cost[stopx][stopy][di][dj]<<" ";
            //  if(cost[stopx][stopy][di][dj]!=0)
            mi=min(cost[stopx][stopy][di][dj],mi);
        }
        //  g<<"\n";
    }
    if(mi==1e9)
        mi=-1;
    g<<mi;
    return 0;
}