Cod sursa(job #612379)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 7 septembrie 2011 11:13:25
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <cstdio>
#include <cstring>
#include <queue>
#define INFI 0x3f3f3f

using namespace std;

bool a[501][501];
char ch[1024];
int c[501][501][8],cost[8][8],dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};
struct str{int x,y,d;};
queue <str> q;

inline int fct(int x,int y)
{
    int aux,f1,f2;
    if (x>y)
    {
        aux=x;
        x=y;
        y=aux;
    }
    f1=x+8-y;
    f2=y-x;
    if (f1<f2)
        return f1;
    else
        return f2;
}
int main()
{
    int n,m,x1,y1,x2,y2,i,j,x,y,d,xx,yy,sol,*nod,*fiu;
    str aux;
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    for (i=0;i<8;++i)
        for (j=0;j<8;++j)
            cost[i][j]=fct(i,j);
    scanf("%d %d %d %d %d %d\n",&n,&m,&x1,&y1,&x2,&y2);
    for (i=1;i<=n;++i)
    {
        fgets(ch,sizeof(ch),stdin);
        for (j=0;j<(m+m);j+=2)a[i][j/2+1]=ch[j]-'0';
    }
    memset(c,0x3f,sizeof(c));
    for (i=0;i<8;++i)
    {
        c[x1][y1][i]=0;
        aux.x=x1;
        aux.y=y1;
        aux.d=i;
        q.push(aux);
    }
    sol=INFI;
    while (!q.empty())
    {
        aux=q.front();
        q.pop();
        x=aux.x;
        y=aux.y;
        d=aux.d;
        nod=&c[x][y][d];
        for (i=0;i<8;++i)
            if (cost[d][i]<3)
            {
                xx=x+dx[i];
                yy=y+dy[i];
                fiu=&c[xx][yy][i];
                if (xx>0&&xx<=n&&yy>0&&yy<=m)
                    if (!a[xx][yy])
                        if (*nod+cost[d][i]<*fiu )
                        {
                            *fiu=*nod+cost[d][i];
                            if (*fiu<sol)
                            {
                                aux.x=xx;
                                aux.y=yy;
                                aux.d=i;
                                q.push(aux);
                            }
                            if (c[x2][y2][i]<sol)
                                sol=c[x2][y2][i];
                        }
            }
    }
    if (sol!=INFI)
        printf("%d\n",sol);
    else
        printf("-1\n");
    return 0;
}