Cod sursa(job #2497508)

Utilizator RadianElevenAdrian Ariotn RadianEleven Data 22 noiembrie 2019 19:46:48
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.04 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;
}