Cod sursa(job #976153)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 22 iulie 2013 17:09:03
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");

#define LE 506
struct trei {
    int x,y,z;
};

trei que[2][LE*LE*60];
trei que2[LE*LE*60];
int dp[LE][LE][8];
int nr[2],xi,yi,xf,yf;
int result;

int xx[]= {-1,-1, 0, 1,1, 1, 0,-1};
int yy[]= { 0 ,1 ,1, 1,0,-1,-1,-1};

trei mk3(int i1,int i2,int i3) {
    trei res;
    res.x=i1,res.y=i2,res.z=i3;
    return res;
}

void dij() {
    bool okz=false;
    trei P;

    for(int l=0; nr[l]&&okz==false; l^=1) {
        int nr2=0;
        for(int i=1; i<=nr[l]&&okz==false; ++i) {

             P=que[l][i];

//cout<<P.x<<" "<<P.y<<" "<<P.z<<'\n';

            if (P.x==xf&&P.y==yf) {
                result=dp[P.x][P.y][P.z];
                okz=true;
                continue;
            }
            if (dp[P.x][P.y][(P.z+8-1)%8]==0)
                que2[++nr2]=mk3(P.x,P.y,(P.z+8-1)%8);

            if (dp[P.x][P.y][(P.z+1)%8]==0)
                que2[++nr2]=mk3(P.x,P.y,(P.z+1)%8);

            if(dp[P.x+xx[P.z]][P.y+yy[P.z]][P.z]==0) {
                dp[P.x+xx[P.z]][P.y+yy[P.z]][P.z]=dp[P.x][P.y][P.z];
                que[l][++nr[l]]=mk3(P.x+xx[P.z],P.y+yy[P.z],P.z);
            }
        }
        for(int i=1; i<=nr2; ++i)
            if (dp[que2[i].x][que2[i].y][que2[i].z]==0){
            que[l^1][++nr[l^1]]=que2[i];
            dp[que2[i].x][que2[i].y][que2[i].z]=dp[P.x][P.y][P.z]+1;
        }
        nr[l]=0;
    }
}
int n,m,i,j;
short int a[LE][LE];

int main() {
    f>>n>>m;
    f>>xi>>yi>>xf>>yf;

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j) f>>a[i][j];

    for(i=0; i<=7; ++i) {
        que[0][++nr[0]]=mk3(xi,yi,i);
        dp[xi][yi][i]=1;
        // cout<<xi<<" "<<yi<<" "<<i<<'\n';
    }

    for(i=0; i<=n+1; ++i)
        for(j=0; j<=m+1; ++j)
            for(int k=0; k<=7; ++k)
                if (i==0||i==n+1||j==0||j==m+1||a[i][j]==1)
                    dp[i][j][k]=-1;

    dij();

  //  cout<<result-1<<'\n';
    g<<result-1<<'\n';

    f.close();
    g.close();
    return 0;
}