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