Cod sursa(job #382854)

Utilizator freak93Adrian Budau freak93 Data 14 ianuarie 2010 21:13:48
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include<fstream>
#include<vector>

using namespace std;

const char iname[]="car.in";
const char oname[]="car.out";
const int maxn=507;
const int INF=(1<<31)-1;

ifstream f(iname);
ofstream g(oname);

template<class T1,class T2,class T3> struct mpair
{
    T1 first;
    T2 second;
    T3 third;
    mpair() : first(T1()), second(T2()), third(T3()) {}
    mpair(const T1& x, const T2& y,const T3& z) : first(x), second(y), third(z) {}
};

template<class F1,class F2,class F3>
inline mpair<F1,F2,F3>
        make_mpair(F1 x,F2 y,F3 z)
{
    return (mpair<F1,F2,F3>(x,y,z) );
}

vector<mpair<int,int,int> > Q[maxn*maxn*2];

int x1,y1,x2,y2,i,j,n,m,dis[maxn][maxn][10],a[maxn][maxn],k;
int dx[12]={0,-1,-1,-1,0,1,1,1,0,-1,-1,-1};
int dy[12]={-1,-1,0,1,1,1,0,-1,-1,-1,0,1};
int cd[12]={8,9,2,3,4,5,6,7,8,9,2,3};

int many,x,y,z;

int main()
{
    f>>n>>m;
    f>>x1>>y1>>x2>>y2;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            f>>a[i][j];

    for(i=0;i<=n+1;++i)
        a[0][i]=a[n+1][i]=a[i][0]=a[i][n+1]=1;

    for(i=0;i<=n+1;++i)
        for(j=0;j<=n+1;++j)
            if(a[i][j]==1)
                for(k=2;k<=9;++k)
                    dis[i][j][k]=-1;
            else
                for(k=2;k<=9;++k)
                    dis[i][j][k]=INF;

    for(k=2;k<=9;++k)
        Q[0].push_back(make_mpair(x1,y1,k)),dis[x1][y1][k]=0;
    many=8;
    for(i=0;many;++i,Q[i-1].clear())
        for(j=0;j<Q[i].size();++j)
        {
            x=Q[i][j].first;
            y=Q[i][j].second;
            z=Q[i][j].third;
            --many;
            if(a[x][y]==1||dis[x][y][z]!=i)
                continue;
            if(dis[x][y][z]<dis[x+dx[z]][y+dy[z]][z])
                dis[x+dx[z]][y+dy[z]][z]=dis[x][y][z],Q[i].push_back(make_mpair(x+dx[z],y+dy[z],z)),++many;
            if(dis[x][y][z]+1<dis[x+dx[z+1]][y+dy[z+1]][cd[z+1]])
                dis[x+dx[z+1]][y+dy[z+1]][cd[z+1]]=dis[x][y][z]+1,Q[i+1].push_back(make_mpair(x+dx[z+1],y+dy[z+1],cd[z+1])),++many;
            if(dis[x][y][z]+1<dis[x+dx[z-1]][y+dy[z-1]][cd[z-1]])
                dis[x+dx[z-1]][y+dy[z-1]][cd[z-1]]=dis[x][y][z]+1,Q[i+1].push_back(make_mpair(x+dx[z-1],y+dy[z-1],cd[z-1])),++many;
            if(dis[x][y][z]+2<dis[x+dx[z+2]][y+dy[z+2]][cd[z+2]])
                dis[x+dx[z+2]][y+dy[z+2]][cd[z+2]]=dis[x][y][z]+2,Q[i+2].push_back(make_mpair(x+dx[z+2],y+dy[z+2],cd[z+2])),++many;
            if(dis[x][y][z]+2<dis[x+dx[z-2]][y+dy[z-2]][cd[z-2]])
                dis[x+dx[z-2]][y+dy[z-2]][cd[z-2]]=dis[x][y][z]+2,Q[i+2].push_back(make_mpair(x+dx[z-2],y+dy[z-2],cd[z-2])),++many;
        }

    x=INF;
    for(k=2;k<=9;++k)
        x=min(x,dis[x2][y2][k]);

    g<<x<<"\n";

    f.close();
    g.close();

    return 0;
}