Cod sursa(job #773781)

Utilizator GrimpowRadu Andrei Grimpow Data 2 august 2012 16:16:52
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <string>
#include<string.h>

#define MAXN 512
#define INF 0x3f3f3f3f

int main(){

  freopen("car.in", "r", stdin);
  freopen("car.out", "w", stdout);

  int N, M, i, j, sx, sy, ex, ey, p, l[2], cq, nq, x, y, d, nx, ny, nd, np, r;
  static int R[MAXN+5][MAXN+5], min[8*MAXN*MAXN+10], Q[2][8*MAXN*MAXN];
  int dx[8]={-1, -1, 0, 1, 1, 1, 0, -1};
  int dy[8]={0, 1, 1, 1, 0, -1, -1, -1};

  scanf("%d%d%d%d%d%d", &N, &M, &sx, &sy, &ex, &ey);
  for(i=1; i<=N; i++)
    for(j=1; j<=M; j++)
      scanf("%d", &(R[i][j]));

  memset(min, INF, sizeof(min));

  for(i=0; i<8; i++){
    p=(i<<18)+(sx<<9)+sy;
    Q[0][i]=p;
    min[p]=0;
  }

  l[0]=i; l[1]=0; cq=0; r=-1;
  while(l[cq]){

    nq=1-cq;    

    for(i=0; i<l[cq]; i++){

      p=Q[cq][i];
      d=p>>18; y=p&511; x=(p>>9)&511;

      if(x==ex && y==ey){
	r=min[p];
	break;
      }
	
      
      nx=x+dx[d];
      ny=y+dy[d];
      np=(d<<18)+(nx<<9)+ny;

      if(0<nx && nx<=N && 0<ny && ny<=M && !R[nx][ny] && min[p]<min[np]){
	min[np]=min[p];
	Q[cq][l[cq]++]=np;
      }

      nd=(d==7)? 0: d+1;
      np=(nd<<18)+(x<<9)+y;
      if(min[np]>min[p]+1){
	min[np]=min[p]+1;
	Q[nq][l[nq]++]=np;
      }

      nd=(d==0)? 7: d-1;
      np=(nd<<18)+(x<<9)+y;
      if(min[np]>min[p]+1){
	min[np]=min[p]+1;
	Q[nq][l[nq]++]=np;
      }

    }
    
    if(r!=-1)
      break;
    
    l[cq]=0; cq=nq;
    
  }

  printf("%d\n", r);

  return 0;

}