Cod sursa(job #238958)

Utilizator ConsstantinTabacu Raul Consstantin Data 3 ianuarie 2009 18:53:59
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include<stdio.h>
#define inf 1000000
struct coada {int l,c;
              char dir;} c[250000];
int i,j,k,l,m,n,t,li,ci,lf,cf,p,q;
int dl[]={0,0,0,1,-1,1,-1,-1,1};
int dc[]={0,1,-1,0,0,1,1,-1,-1};
int cost[]={0,1,2,3};
long long int x[511][511];
int cmp(char i,int f);
int main(){
FILE *f=fopen("car.in","r");
fscanf(f,"%d %d" ,&n,&m);
fscanf (f,"%d %d %d %d",&li,&ci,&lf,&cf);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
        {fscanf(f,"%d",&k);
        if(k)
                x[i][j]=-1;
        else
                x[i][j]=inf;}
fclose(f);
p=q=1;
for(i=1;i<=n;i++)
        x[i][0]=x[i][m+1]=-1;
for(i=1;i<=m;i++)
        x[0][i]=x[n+1][i]=-1;
x[0][0]=-1;
x[n+1][0]=-1;
x[0][m+1]=-1;
x[n+1][m+1]=-1;
c[p].l=li;c[p].c=ci;
x[lf][cf]=inf;x[li][ci]=0;
for(i=1;i<=8;i++)
        {if(x[c[p].l+dl[i]][c[p].c+dc[i]]==inf)
                {q++;
                c[q].l=c[p].l+dl[i];
                c[q].c=c[p].c+dc[i];
                c[q].dir=i;
                x[c[q].l][c[q].c]=0;
                }
       }
       
p++;
FILE *g=fopen("car.out","w");
if(x[lf][cf]!=inf)
        {fprintf(g,"%d",x[lf][cf]);
        fclose(g);
        return 0;}
while(p<=q)
        {for(i=1;i<=8;i++)
                {l=c[p].l+dl[i];
                k=c[p].c+dc[i];
                if(x[l][k]!=-1)
                        {t=cmp(c[p].dir,i);
                                if(t+x[c[p].l][c[p].c]<x[l][k])
                                        {x[l][k]=t+x[c[p].l][c[p].c];
                                        q++;
                                        c[q].l=l;
                                        c[q].c=k;
                                        c[q].dir=i;
                                        }
                        }
             }
        p++;
        }
if(!x[lf][cf])
        fprintf(g,"%d",-1);
else
        fprintf(g,"%d",x[lf][cf]);
return 0;}
int cmp(char i,int f){
int a;
a=int (i);
if(a==f)return 0;
else
if(a==1)
        {if(f==6||f==5)
                return 1;
        else
        if(f==3||f==4)
                return 2;
        else
        if(f==8||f==7)
                return 3;
       else
        return 4;
        }
else
if(a==2)
        {if(f==7||f==8)return 1;
        else
        if(f==3||f==4)return 2;
        else
        if(f==5||f==6)return 3;
        else
        return 4;
        }
else
if(a==3)
        {if (f==8||f==5)return 1;
        else
        if(f==1||f==2)return 2;
        else
        if(f==7||f==6)return 3;
        else return 4;}
else
if(a==4)
        {if(f==6||f==7) return 1;
        else
        if(f==1||f==2)return 2;
        else
        if(f==8||f==5) return 3;
        else
        return 4;
        }
else
if(a==5)
        {if(f==1||f==4)return 1;
        else
        if(f==6||f==8)return 2;
        else
        if(f==2||f==4)return 3;
        else
        return 4;
        }
else
if(a==6)
        {if(f==4||f==1)return 1;
        else
        if(f==7||f==5)return 2;
        else
        if(f==3||f==2)return 3;
        else
        return 4;}
else
if(a==7){
        if(f==4||f==2)return 1;
        else
        if(f==6||f==8)return 2;
        else
        if(f==1||f==3)return 3;
        else
        return 4;
        }
else
if(a==8)
        {if(f==2||f==3)return 1;
        else
        if(f==5||f==7)return 2;
        else
        if(f==4||f==1)return 3;
        else
        return 4;}
}