Cod sursa(job #2494768)

Utilizator RadianElevenAdrian Ariotn RadianEleven Data 18 noiembrie 2019 13:13:27
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.66 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;
};
queue < Nod> coada;

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


   // mak[startx][startx] = 1;
    coada.push({startx,starty,{0, 0}});
    //coada.push2(make_pair(startx,starty));
    Nod elem={startx, starty};

    int inext, jnext;
    while(!coada.empty())
    {
        elem=coada.front();

        int icurent = coada.front().x;
        int jcurent = coada.front().y;
        Dir dirr=elem.commingdir;
       // cout<<dirr.dirx<<" "<<dirr.diry<<"\n";
        //viz[icurent][jcurent]=1;
        coada.pop();
        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];
                        Nod child;
                        child.x=inext;
                        child.y=jnext;
                        Dir d;
                        d.dirx=inext-startx;
                        d.diry=-(jnext-starty);
                        child.commingdir=d;
                        cost[inext][jnext][d.dirx+1][d.diry+1]=0;
                        coada.push(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";
                        Nod child;
                        child.x=inext;
                        child.y=jnext;
                        Dir d;
                        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;
                        }
                        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]+0 ) )
                            cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+0 , coada.push(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 , coada.push(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 , coada.push(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]+3))
                            cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+3 , coada.push(child);
                        else if(cdir.dirx==-1&& abs(cdir.diry)==0 &&
                                (cost[inext][jnext][d.dirx+1][d.diry+1]>cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+4))
                            cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+4 , coada.push(child);

                }



            }


        }

    }
}
int main()
{
    f>>n>>m>>startx>>starty>>stopx>>stopy;



    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            f>>mak[i][j];
            if(mak[i][j]==1)
                mak[i][j]=-1;
        }
    }
    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;
}