Cod sursa(job #377320)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 23 decembrie 2009 23:34:07
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <queue>
#define Nmax 515
#define INF 2147000000
using namespace std;

int dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};
int a[Nmax][Nmax];
int d[8][Nmax][Nmax];
int n,m,i,j,k,st,turns,nr;
int x,y,xi,yi,xf,yf,xx,yy,dir,dir2;
queue< int > Q[2];

int main(){
	freopen("car.in","r",stdin);
   freopen("car.out","w",stdout);
   scanf("%d%d",&n,&m);
   scanf("%d%d%d%d",&xi,&yi,&xf,&yf);
   for(i=1;i<=n;++i)
   	for(j=1;j<=m;++j) scanf("%d",&a[i][j]);

   memset(d,0x3f,sizeof(d));
   for(k=0;k<8;++k){
   	  Q[0].push(xi+(yi<<9)+(k<<18));
      d[k][xi][yi]=0;
   }
   st=1; turns=0;
   while(!Q[st^1].empty()){
   	for(; !Q[st^1].empty(); Q[st^1].pop() ){
      	nr=Q[st^1].front();
         x=nr&511;
         y=(nr>>9)&511;
         dir=nr>>18;
         if( x==xf && y==yf ){
         	printf("%d\n",turns);
            return 0;
         }

         xx=x+dx[dir]; yy=y+dy[dir];
         if(xx>0 && yy>0 && xx<=n && yy<=m && !a[xx][yy])
	         if(d[dir][xx][yy]>turns){
            	d[dir][xx][yy]=turns;
               Q[st^1].push(xx+(yy<<9)+(dir<<18));
            }

         dir2=(dir+1)%8;
         if(d[dir2][x][y] > turns+1){
         	d[dir2][x][y]=turns+1;
            Q[st].push(x+(y<<9)+(dir2<<18));
         }
         dir2=(dir+7)%8;
         if(d[dir2][x][y] > turns+1){
         	d[dir2][x][y]=turns+1;
            Q[st].push(x+(y<<9)+(dir2<<18));
         }
      }
      turns++;
      st^=1;
   }
   printf("%d\n",-1);
   return 0;
}