Cod sursa(job #396908)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 16 februarie 2010 06:43:24
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <stdlib.h>
#include <stdio.h>
#include <deque>
#define INF 0x7f7f7f7f
#define N 501

using namespace std;
bool a[N][N];
int cost[N][N][8];
int delta[8][8];
int dx[8]={0,1,1, 1, 0,-1,-1,-1};
int dy[8]={1,1,0,-1,-1,-1, 0, 1};

struct nod
{int x,y,prev;
 nod(int a,int b,int c)
 {x=a;y=b;prev=c;
 }
 nod()
 {}
};

int f(int x,int y)//costul dintre doua directii
                  //f(delta)=0 1 2 3 4 3 2 1
{return abs(4-abs(4-abs(x-y)));
}

int main ()
{freopen("car.in","r",stdin);
 freopen("car.out","w",stdout);
 int sx,sy,fx,fy,x,tx,ty;
 int i,j,k,n,m,min,aux,c,*d;
 deque<nod> q;
 nod p;

 for (i=0;i<8;i++)
 {for (j=i;j<8;j++)
  {delta[i][j]=delta[j][i]=f(i,j);
  }
 }
 
 scanf("%d %d",&n,&m);
 scanf("%d %d %d %d",&sx,&sy,&fx,&fy);
 
 for (i=1;i<=n;i++)
 {for (j=1;j<=m;j++)
  {scanf("%d",&x);
   a[i][j]=x;
   for (k=0;k<8;k++)
   {cost[i][j][k]=INF;
   }
  }
 }
 for (i=0;i<=n+1;i++){a[i][0]=1;a[i][m+1]=1;}
 for (j=0;j<=m+1;j++){a[0][j]=1;a[n+1][j]=1;}
 a[sx][sy]=1;
 
 for (i=0;i<8;i++)
 {cost[sx][sy][i]=0;
  tx=dx[i]+sx;
  ty=dy[i]+sy;
  if(!a[tx][ty])
  {cost[tx][ty][i]=0;
   q.push_back(nod(tx,ty,i));
  }
 }

 while(!q.empty())
 {p=q.front();q.pop_front();
  c=cost[p.x][p.y][p.prev];
  d=delta[p.prev];
  for (i=7&(p.prev+6);i<(7&(p.prev+2));i++)
  {tx=p.x+dx[i];
   ty=p.y+dy[i];

   if(!a[tx][ty])
   {if(cost[tx][ty][i]>(aux=c+(*(d+i))))
    {cost[tx][ty][i]=aux;
     q.push_back(nod(tx,ty,i));
    }
   }
  }
 }
 
 min=INF;
 for (i=0;i<8;i++)
 {if(cost[fx][fy][i]<min)
  {min=cost[fx][fy][i];
  }
 }
 if(min==INF)
 {printf("-1");
 }
 else
 {printf("%d",min);
 }
 
 return 0;
}