Cod sursa(job #1612335)

Utilizator gapdanPopescu George gapdan Data 24 februarie 2016 20:07:11
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <cstdio>
#include <queue>
#define min(a,b) (a<b ? a:b)
#define inf 999999999
#define NR 510

using namespace std;

int i,j,n,m,x,y,X,Y,xact,yact,Min,Dir,d,xv,yv,o;
bool a[NR][NR];
int dp[NR][NR][8];
int dx[]={1, 1, 0, -1, -1, -1, 0, 1};
int dy[]={0, 1, 1,  1,  0, -1,-1,-1};
struct punct
{
    int x,y,d;
}T;
queue<punct>q;
int main()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    scanf("%d%d",&n,&m);
    scanf("%d%d%d%d",&x,&y,&X,&Y);

    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
            {
                scanf("%d",&a[i][j]);
                 a[i][j]=1-a[i][j];
            }
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
           for(int w=0;w<8;++w) dp[i][j][w]=inf;

    for (i=0; i<8; ++i)
    {
        punct T;
        T.x=x; T.y=y; T.d=i;
        q.push(T);
        dp[x][y][i]=0;
    }

    while (! q.empty())
    {
        T=q.front(); q.pop();
        xv=T.x+dx[T.d]; yv=T.y+dy[T.d];
        xact=T.x; yact=T.y; d=T.d; Dir=T.d;

        if (a[xv][yv] && dp[xv][yv][d] > dp[xact][yact][d])
        {
            dp[xv][yv][d]=dp[xact][yact][d];
            T.x=xv; T.y=yv; T.d=d;
            q.push(T);
        }

        d=(Dir+7)%8;
        if (dp[xact][yact][Dir]+1<dp[xact][yact][d])
        {
            dp[xact][yact][d]=dp[xact][yact][Dir]+1;
            T.x=xact; T.y=yact; T.d=d;
            q.push(T);
        }
        d=(Dir+9)%8;
        if (dp[xact][yact][Dir]+1<dp[xact][yact][d])
        {
            dp[xact][yact][d]=dp[xact][yact][Dir]+1;
            T.x=xact; T.y=yact; T.d=d;
            q.push(T);
        }
    }

    Min=inf;
    for (i=0; i<8; ++i)
        Min=min(Min, dp[X][Y][i]);

 if (Min==inf) printf("-1\n");
        else printf("%d\n",Min);
    return 0;
}