Cod sursa(job #587801)

Utilizator Smaug-Andrei C. Smaug- Data 5 mai 2011 21:51:17
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>
#include <string>

#define MAXN 501

typedef struct Qmem {
  int x, y, d;
} Qmem;

int main(){

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

  int N, M, sx, sy, ex, ey, i, j, k, cq, nq, ax, ay, dir, res;
  int dx[8]={-1, -1, 0, 1, 1, 1, 0, -1}, 
      dy[8]={0, 1, 1, 1, 0, -1, -1, -1};
  static int R[MAXN][MAXN], m[8][MAXN][MAXN], v[8][MAXN][MAXN], l[2];
  static Qmem Q[2][2*MAXN*MAXN], c;

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

  sx--; sy--; ex--; ey--;

  memset(v, 0, sizeof(v));

  for(i=0; i<8; i++){
    Q[0][i].x=sx;
    Q[0][i].y=sy;
    Q[0][i].d=i;
    m[i][sx][sy]=0;
    v[i][sx][sy]=1;
  }

  res=-1;
  l[0]=7; l[1]=0; cq=0;
  while(l[cq]){
    nq=1-cq;

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

      c=Q[cq][k];
      ax=c.x+dx[c.d];
      ay=c.y+dy[c.d];

      if(c.x==ex && c.y==ey){
	res=m[c.d][c.x][c.y];
	break;
      }

      if(0<=ax && ax<N && 0<=ay && ay<M)
	if(!R[ax][ay] && (!v[c.d][ax][ay] || m[c.d][c.x][c.y]<m[c.d][ax][ay])){
	  v[c.d][ax][ay]=1;
	  m[c.d][ax][ay]=m[c.d][c.x][c.y];
	  Q[cq][l[cq]].x=ax;
	  Q[cq][l[cq]].y=ay;
	  Q[cq][l[cq]].d=c.d;
	  l[cq]++;
	}

      dir=c.d+1;
      if(dir==8)
	dir=0;
      if(!v[dir][c.x][c.y]){
	v[dir][c.x][c.y]=1;
	m[dir][c.x][c.y]=m[c.d][c.x][c.y]+1;
	Q[nq][l[nq]].x=c.x;
	Q[nq][l[nq]].y=c.y;
	Q[nq][l[nq]].d=dir;
	l[nq]++;
      }
      
      dir=c.d-1;
      if(dir==-1)
	dir=7;
      if(!v[dir][c.x][c.y]){
	v[dir][c.x][c.y]=1;
	m[dir][c.x][c.y]=m[c.d][c.x][c.y]+1;
	Q[nq][l[nq]].x=c.x;
	Q[nq][l[nq]].y=c.y;
	Q[nq][l[nq]].d=dir;
	l[nq]++;
      }
    }

    if(res!=-1)
      break;

    l[cq]=0;
    cq=nq;

  }

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

  return 0;

}