Cod sursa(job #2288142)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 22 noiembrie 2018 21:23:45
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <bits/stdc++.h>



using namespace std;



ifstream fin("car.in");

ofstream fout("car.out");



const int Nmax=505;

const int oo=2e9;

int n,m,xi,yi,xf,yf;

int a[Nmax][Nmax];

int drum[Nmax][Nmax][10];

int dx[] = {-1,-1,0,1,1,1,0,-1};

int dy[] = {0,1,1,1,0,-1,-1,-1};



struct Coada

{

    int x,y,cost,dir;

};



queue<Coada>Q;

queue<Coada>q;



void Init()

{

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

            for(int k=0;k<8;k++)

                drum[i][j][k]=oo;

}



inline bool Verificare(int x,int y)

{

    return x>=1 && x<=n && y>=1 && y<=m && a[x][y]==0;

}



void Build()

{

    for(int k=0;k<8;k++)

        Q.push({xi,yi,0,k});





    Coada x,y;

    while(!Q.empty())

    {

        while(!Q.empty())

        {

            x=Q.front();

            Q.pop();



            y.cost=x.cost;

            y.dir=x.dir;

            y.x=x.x+dx[x.dir];

            y.y=x.y+dy[x.dir];



            if(Verificare(y.x,y.y) && drum[y.x][y.y][y.dir]>y.cost)

            {

                drum[y.x][y.y][y.dir]=y.cost;

                Q.push(y);

            }



            y.x=x.x;

            y.y=x.y;

            y.cost=x.cost+1;

            y.dir=x.dir+1;

            if(y.dir==8)y.dir=0;



            if(Verificare(y.x,y.y) && drum[y.x][y.y][y.dir]>y.cost)

            {

                drum[y.x][y.y][y.dir]=y.cost;

                q.push(y);

            }



            y.dir=x.dir-1;

            if(y.dir<0)y.dir=7;



            if(Verificare(y.x,y.y) && drum[y.x][y.y][y.dir]>y.cost)

            {

                drum[y.x][y.y][y.dir]=y.cost;

                q.push(y);

            }

        }



        while(!q.empty())

        {

            x=q.front();

            q.pop();

            Q.push(x);

        }

    }

}



int main()

{

    fin>>n>>m>>xi>>yi>>xf>>yf;



    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

            fin>>a[i][j];



    Init();

    Build();



    int minim=oo;

    for(int i=0;i<8;i++)

        minim=min(minim,drum[xf][yf][i]);



    if(minim==oo)fout<<"-1\n";

    else fout<<minim<<"\n";



    fin.close();

    fout.close();

    return 0;

}