Cod sursa(job #2436692)

Utilizator CharacterMeCharacter Me CharacterMe Data 6 iulie 2019 18:20:53
Problema Car Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <queue>
#define inf 1000000000
#include<algorithm>
using namespace std;
ifstream fin ("car.in");
ofstream fout("car.out");
int di[8]={1,1,0,-1,-1,-1,0,1};
int dj[8]={0,1,1,1,0,-1,-1,-1};
struct punct{int x;int y;int d;} aux,p;
queue<punct> l,q;
int i,j,h,x1,x2,y1,y2,n,m,a[512][512],d[512][512][10];
int main ()
{
    fin>>n>>m;
    fin>>x1>>y1>>x2>>y2;
    for(i=1;i<=n;i++) for(j=1;j<=m;j++){fin>>a[i][j];a[i][j]=1-a[i][j];for(h=0;h<=7;h++) d[i][j][h]=inf;}
    for(i=0;i<=7;i++)
    {
        aux.x=x1;aux.y=y1;aux.d=i;
        d[x1][y1][i]=0;
        q.push(aux);
    }
    while(!q.empty())
    {
        while(!q.empty())
        {
            aux=q.front();q.pop();
         //   fout<<aux.x<<" "<<aux.y<<" "<<aux.d<<"\n";
            if(aux.x==x2&&aux.y==y2){fout<<d[aux.x][aux.y][aux.d];return 0;}
            p=aux;p.x+=di[p.d];p.y+=dj[p.d];
            if(a[p.x][p.y]==1&&d[p.x][p.y][p.d]>d[aux.x][aux.y][aux.d])
            {
                d[p.x][p.y][p.d]=d[aux.x][aux.y][aux.d];
                q.push(p);
            }
            p=aux;p.d=(p.d+1)%8;
            if(d[p.x][p.y][p.d]>d[aux.x][aux.y][aux.d]+1)
            {
                d[p.x][p .y][p.d]=d[aux.x][aux.y][aux.d]+1;
                l.push(p);
            }
            p=aux;p.d-=1;if(p.d==-1) p.d=7;
            if(d[p.x][p.y][p.d]>d[aux.x][aux.y][aux.d]+1)
            {
                d[p.x][p.y][p.d]=d[aux.x][aux.y][aux.d]+1;
                l.push(p);
            }
            while(!l.empty())
        {
            q.push(l.front());
            l.pop();
        }
        }
    }
    fout<<-1;
    return 0;
}