Cod sursa(job #587444)

Utilizator Smaug-Andrei C. Smaug- Data 4 mai 2011 20:40:42
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define INF 1000000

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

int A[3][3]={{-1,0,1},{-2,0,2},{-3,4,3}};


void add(int C[501][501], int R[501][501], int N, int M, qm a, qm *Q, int *nqp){
  
  int i, j, aux;

  for(i=-1; i<=1; i++){
    for(j=-1; j<=1; j++){
      if((i||j) && 0<=a.x+i && a.x+i<N && 0<=a.y+j && a.y+j<M && !R[a.x+i][a.y+j]){
	aux=abs(A[i+1][j+1]-a.d);
	aux=min(aux, 8-aux);
	if(C[a.x][a.y]+aux < C[a.x+i][a.y+j]){
	  C[a.x+i][a.y+j]=C[a.x][a.y]+aux;
	  Q[(*nqp)].x=a.x+i;
	  Q[(*nqp)].y=a.y+j;
	  Q[(*nqp)].d=A[i+1][j+1];
	  (*nqp)++;
	}
      }
    }
  }

  

}

int main(){

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

  static int N, M, R[501][501], C[501][501];
  int sx, sy, ex, ey, i, j, nqp, cqp;
  static qm Q1[501*501], Q2[501*501], *cq, *nq, *aux;

  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--;

  for(i=0; i<N; i++)
    for(j=0; j<M; j++)
      C[i][j]=INF;

  C[sx][sy]=0;

  cq=Q1; nq=Q2; cqp=0; nqp=0;

  for(i=-1; i<=1; i++){
    for(j=-1; j<=1; j++){
      if((i||j) && 0<=sx+i && sx+i<N && 0<=sy+j && sy+j<M && !R[sx+i][sy+j]){
	cq[nqp].x=sx+i;
	cq[nqp].y=sy+j;
	cq[nqp].d=A[i+1][j+1];
	C[sx+i][sy+j]=0;
	cqp++;
      }
    }
  }
    
  while(cqp){
    for(i=0; i<cqp; i++)
      add(C, R, N, M, cq[i], nq, &nqp);

    /*for(i=0; i<N; i++){
      for(j=0; j<M; j++)
      printf("%3d ", C[i][j]);
      printf("\n");
      }*/

    cqp=nqp; nqp=0; aux=cq; cq=nq; nq=aux;
  }

  printf("%d\n", (C[ex-1][ey-1]!=INF)? C[ex-1][ey-1]: -1);

  return 0;

}