Cod sursa(job #976141)

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

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

trei que[2][LE*LE*60];
int dp[LE][LE][8];
bool viz[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;

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

            trei 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) {
             //   dp[P.x][P.y][(P.z+8-1)%8]=dp[P.x][P.y][P.z]+1;
           //     que[l^1][++nr[l^1]]=mk3(P.x,P.y,(P.z+8-1)%8);
         //   }
            if (dp[P.x][P.y][(P.z+1)%8]==0) {
                dp[P.x][P.y][(P.z+1)%8]=dp[P.x][P.y][P.z]+1;
                que[l^1][++nr[l^1]]=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);
            }
        }
        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;
}