Cod sursa(job #514525)

Utilizator webspiderDumitru Bogdan webspider Data 18 decembrie 2010 21:46:09
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.28 kb
#include <stdio.h>
#include <stdlib.h>

/*
 * 0 1 2
 * 7 C 3
 * 6 5 4
 *
 */

const int maxN = 500;

bool inQueue[maxN][maxN][8];
int isWall[maxN][maxN];

const int dx[8] = { -1, -1, -1,  0,  1,  1,  1,  0 };
const int dy[8] = { -1,  0,  1,  1,  1,  0, -1, -1 };
const int tr[8] = {  0,  1,  2,  3,  4,  5,  6,  7 };
const int NB = 8;

const int dDL[5] = { 1, 2, 2, 2, 1 };
const int dD[5][2] = {
/* Dist\Idx    0    1   */
/*   0    */{  0,  -1   },
/*   1    */{  1,   7   },
/*   2    */{  2,   6   },
/*   3    */{  3,   5   },
/*   4    */{  4,  -1   }  };       

const int rotCost[8] = 
/*        0  1  2  3  4  5  6  7  */
/* 0 */{  0, 1, 2, 3, 4, 3, 2, 1  };   
/* All other pairs can be determined by translation */

short int N, M;

typedef struct Pos {
  short int X, Y;
  short int rotation;
  int cost;
  Pos *next;
} Pos;

Pos *queueHead, *queueTail;
Pos *distQueueHead[6];
Pos *distQueueTail[6];
Pos *usedToFree;

short int startX, startY, endX, endY;

Pos * _newPos(int X, int Y, int rotation, int cost) {
  Pos *aux = (Pos *) malloc( sizeof(Pos) );
  aux->X = X; aux->Y = Y; 
  aux->rotation = rotation;
  aux->cost = cost;
  aux->next = NULL;
  return aux;
}

bool atEnd(Pos* position) {
  return position->X == endX && position->Y == endY;
}

void shiftDistQueueHeads() {
  for ( int i = 1; i < 6; i++ ) {
    distQueueHead[i-1] = distQueueHead[i];
    distQueueTail[i-1] = distQueueTail[i];
  }
  distQueueHead[5] = distQueueTail[5] = NULL;
}

int rotationCost(int from, int to) {
  return rotCost[ abs(from - to) ];
}

Pos * _newPosFromTransposition(Pos *pos, int direction) {
  return _newPos( pos->X + dx[direction], pos->Y + dy[direction],
                  tr[direction], pos->cost + rotationCost(pos->rotation, tr[direction]) );
}

bool isInQueue(Pos *pos) {
  return inQueue[pos->X][pos->Y][pos->rotation];
}

bool isValidPosition(Pos *pos) {
  return pos->X >= 0 && pos->X < N && 
         pos->Y >= 0 && pos->Y < M &&
         !isWall[pos->X][pos->Y];
}

bool isValid(Pos *pos) {
  return isValidPosition(pos) && !isInQueue(pos);
}

void pushOnQueue(Pos *node, int dist) {
  if (distQueueTail[dist] != NULL) {
    distQueueTail[dist]->next = node;
    distQueueTail[dist] = node;
  } else {
    distQueueTail[dist] = node;
    distQueueHead[dist] = node;
  }
  int prevQueue = dist-1;
  int nextQueue = dist+1;
  while (prevQueue >= 0 && distQueueTail[prevQueue] == NULL) prevQueue--;
  while (nextQueue <= 5 && distQueueTail[nextQueue] == NULL) nextQueue++;

  if (prevQueue >= 0 && distQueueTail[prevQueue] != NULL)
    distQueueTail[prevQueue]->next = distQueueHead[dist];
  if (nextQueue <= 5 && distQueueHead[nextQueue] != NULL)
    distQueueTail[dist]->next = distQueueHead[nextQueue];

  inQueue[node->X][node->Y][node->rotation] = true;
}

void printNode(Pos *node) {
  printf("(%d ,%d) [%d %d]\n", node->X, node->Y, node->rotation, node->cost);
}

Pos* nextNotNullQueueHead(int l) {
  while ( distQueueHead[l+1] == NULL && l < 5 ) l++;
  return distQueueHead[l+1];
}

int main()
{
  freopen("car.in","r",stdin);
  freopen("car.out","w",stdout);
  
  scanf("%hd %hd\n%hd %hd %hd %hd\n", &N, &M, &startX, &startY, &endX, &endY);
  startX--; startY--; endX--; endY--;
  for (int i = 0; i < N; i++) 
    for ( int j = 0; j < M; j++)
      scanf("%d", &isWall[i][j]);
  
  for (int i = 0; i < 8; i++) {
    Pos *currentPos = _newPos(startX, startY, i, 0);
    pushOnQueue(currentPos, 0);
  }
   
  queueHead = distQueueHead[0];
  int cDist = 0;
  Pos *child;

  while (queueHead != NULL && !atEnd(queueHead)) {
    //printNode(queueHead);
    for (int d = 0; d < dDL[cDist]; d++) {
      child = _newPosFromTransposition(queueHead, (dD[cDist][d]+queueHead->rotation)%8);
      if ( isValid(child) ) {
        pushOnQueue(child, child->cost - queueHead->cost + 1);        
      } else {
        free(child);
      }   
    }
    
    usedToFree = queueHead;
    queueHead = queueHead->next;

    if ( cDist == 4 ) {
      if (nextNotNullQueueHead(0) != NULL && queueHead == nextNotNullQueueHead(0)) {
        while (distQueueHead[0] != queueHead)
          shiftDistQueueHeads();
        cDist = 0;
        free(usedToFree);
      }
    } else {
      if (queueHead == nextNotNullQueueHead(0)) {
        queueHead = distQueueHead[0];
        cDist++;
      }
    }
  }

  printf("%d\n", queueHead!= NULL ? queueHead->cost : -1);
  return 0;
}