Cod sursa(job #1306061)

Utilizator serban_ioan97Ciofu Serban serban_ioan97 Data 30 decembrie 2014 14:51:56
Problema Car Scor 10
Compilator cpp Status done
Runda tema_vacanta_iarna Marime 2.01 kb
#include <cstdio>
#include <queue>
#define oo 0x3f3f3f3f
#define dimmax 505

using namespace std;

struct car
{
    int x, y;
    short d;
}X;

queue <car> q;

int dx[]={1, 1, 0, -1, -1, -1, 0, 1};
int dy[]={0, 1, 1,  1,  0, -1,-1,-1};

bool a[dimmax][dimmax];
int i, j, m, n, k, direction;
int cost[dimmax][dimmax][9];
int xs, ys, xd, yd, xa, ya, xv, yv;

int main()
{
    freopen("car.in", "rt", stdin);
    freopen("car.out", "wt", stdout);

    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &xs, &ys, &xd, &yd);

    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(k=0; k<8; ++k)
                cost[i][j][k]=oo;

    for(i=0; i<8; ++i)
    {
        X.x=xs; X.y=ys;
        X.d=i;
        q.push(X);
    }
    int d, Dir;
    while(!q.empty())
    {
        X=q.front(); q.pop();
        xv=X.x+dx[X.d]; yv=X.y+dy[X.d];
        xa=X.x; ya=X.y;
        d=X.d; Dir=X.d;
        //daca mergem in alte directii decat la 45 de grade la stanga si dreapta fata de
        //directia din care venim, drumul parcurs va avea un cost mai mare si inutil pentru a
        //ajunge in acelasi punct de coordonate x si y
        if (a[xv][yv] && cost[xv][yv][d]>cost[xa][ya][d])
        {
            cost[xv][yv][d]=cost[xa][ya][d];
            X.x=xv; X.y=yv; X.d=d;
            q.push(X);
        }
        d=(Dir+7)%8;
        if (cost[xa][ya][Dir]+1<cost[xa][ya][d])
        {
            cost[xa][ya][d]=cost[xa][ya][Dir]+1;
            X.x=xa; X.y=ya; X.d=d;
            q.push(X);
        }
        d=(Dir+9)%8;
        if (cost[xa][ya][Dir]+1<cost[xa][ya][d])
        {
            cost[xa][ya][d]=cost[xa][ya][Dir]+1;
            X.x=xa; X.y=ya; X.d=d;
            q.push(X);
        }
    }

    int minn=oo;
    for(i=0; i<8; ++i)
    minn=min(minn, cost[xd][yd][i]);
    if(minn==oo) printf("-1\n");
    else printf("%d\n", minn);

    return 0;
}