Cod sursa(job #969183)

Utilizator misinozzz zzz misino Data 3 iulie 2013 19:08:42
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<fstream>
#include<queue>
#define INF 1000000000
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int mini,xn,yn,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[2];
int dy[]={0,1,1,1,0,-1,-1,-1};
int dx[]={1,1,0,-1,-1,-1,0,1};
int ein(int x,int y)
{
    if(x<1||y<1||x>n||y>m||drum[x][y])
    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)
    {
        t.x=xi;
        t.y=yi;
        t.d=i;
        a[t.x][t.y][i]=0;
        c[0].push(t);
    }
    while(1)
    {
        for(i=0;i<=1;++i)
        if(!c[i].empty())
        break;
        if(i>1)
        break;
        x=c[i].front().x;
        y=c[i].front().y;
        d=c[i].front().d;
        c[i].pop();
        xn=x+dx[d];
        yn=y+dy[d];
        if(ein(xn,yn)&&a[xn][yn][d]>a[x][y][d])
        {
            a[xn][yn][d]=a[x][y][d];
            c[0].push((dr){xn,yn,d});
        }
        if(a[x][y][(d+9)&7]>a[x][y][d]+1)
        {
            a[x][y][(d+9)&7]=a[x][y][d]+1;
            c[1].push((dr){x,y,(d+9)&7});
        }
        if(a[x][y][(d+7)&7]>a[x][y][d]+1)
        {
            a[x][y][(d+7)&7]=a[x][y][d]+1;
            c[1].push((dr){x,y,(d+7)&7});
        }
    }
    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;
}