Cod sursa(job #874290)

Utilizator misinozzz zzz misino Data 8 februarie 2013 08:56:34
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<fstream>
#include<queue>
#define INF 1000000000
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int mini,x,y,d,x2,y2,xi,yi,xf,yf,i,j,k,n,m,drum[505][505],a[505][505][9];
struct dr{int x,y,d;};
dr t;
queue<dr>c;
int cost[][8]={
{0,1,2,3,4,3,2,1},
{1,0,1,2,3,4,3,2},
{2,1,0,1,2,3,4,3},
{3,2,1,0,1,2,3,4},
{4,3,2,1,0,1,2,3},
{3,4,3,2,1,0,1,2},
{2,3,4,3,2,1,0,1},
{1,2,3,4,3,2,1,0},
};
int dx[]={0,-1,-1,-1,0,1,1,1};
int dy[]={1,1,0,-1,-1,-1,0,1};
int ein(int x,int y)
{
    if(x<1||y<1||x>n||y>m)
    return 0;
    return 1;
}
int main()
{
    f>>n>>m>>xi>>yi>>xf>>yf;
    for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)
    f>>drum[i][j];
    for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)
    for(k=0;k<=8;++k)
    a[i][j][k]=INF;
    for(i=0;i<8;++i)
    if(ein(xi+dx[i],yi+dy[i])&&!drum[xi+dx[i]][yi+dy[i]])
    {
        t.x=xi+dx[i];
        t.y=yi+dy[i];
        t.d=i;
        a[t.x][t.y][i]=0;
        c.push(t);
    }
    while(!c.empty())
    {
        x=c.front().x;
        y=c.front().y;
        d=c.front().d;
        c.pop();
        for(i=0;i<8;++i)
        {
            x2=x+dx[i];
            y2=y+dy[i];
            if(ein(x2,y2)&&!drum[x2][y2]&&a[x][y][d]+cost[i][d]<a[x2][y2][i])
            {
                a[x2][y2][i]=a[x][y][d]+cost[i][d];
                t.x=x2;
                t.y=y2;
                t.d=i;
                c.push(t);
            }
        }
    }
    mini=INF;
    for(i=0;i<=7;++i)
    {
        if(a[xf][yf][i]<mini)
        mini=a[xf][yf][i];
    }
    if(mini==INF)
    mini=-1;
    g<<mini<<'\n';
    return 0;
}