Cod sursa(job #2260502)

Utilizator 12222Fendt 1000 Vario 12222 Data 15 octombrie 2018 08:40:10
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 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;
}