#include <stdio.h>
#include <list>
using namespace std;
enum { maxsize = 502, dirs = 8 };
const int dir[dirs][2] = //clockwise
{
{ -1, -1 },
{ -1, 0 },
{ -1, 1 },
{ 0, 1 },
{ 1, 1 },
{ 1, 0 },
{ 1, -1 },
{ 0, -1 }
};
const int next[dirs] = { 1, 2, 3, 4, 5, 6, 7, 0 },
prev[dirs] = { 7, 0, 1, 2, 3, 4, 5, 6 };
int rows, cols;
int sr, sc, er, ec;
bool bad[maxsize][maxsize];
int reached[maxsize][maxsize][dirs]; //cost we reached that node with
list<int> node[2]; //node[cost % 2] is of cost cost; node[(cost + 1) % 2] is of cost cost+1;
int ans;
//int adds;
inline int compress(int r, int c, int d)
{
return ((r * maxsize) + c) * dirs + d;
}
inline void decompress(int node, int &r, int &c, int &d)
{
d = node % dirs;
node /= dirs;
r = node / maxsize;
c = node % maxsize;
}
inline void add_nocheck(int cost, int r, int c, int d)
{
if(reached[r][c][d] > cost)
{
/*
if(reached[r][c][d] != 0x3f3f3f3f)
printf("r %d c %d d %d disgust (old %d now %d)\n",
r, c, d, reached[r][c][d], cost);
*/
reached[r][c][d] = cost;
node[cost % 2].push_back(compress(r, c, d));
//adds++;
}
}
/**
* adds only if r and c are valid
*/
inline void attempt_add(int cost, int r, int c, int d)
{
if(r >= 0 && r < rows && c >= 0 && c < cols)
if(!bad[r][c])
add_nocheck(cost, r, c, d);
}
void go()
{
int i, tmp, r, c, d;
int cost = 0;
memset(reached, 0x3f, sizeof(reached));
if(!bad[sr][sc])
{
for(i = 0; i < dirs; i++)
add_nocheck(0, sr, sc, i);
}
while(!node[0].empty() || !node[1].empty())
{
if(node[cost % 2].empty())
cost++;
tmp = *(node[cost % 2].begin());
node[cost % 2].pop_front();
decompress(tmp, r, c, d);
if(r == er && c == ec)
break; //ans is current cost
if(cost > reached[r][c][d]) //stale node, don't bother
continue;
//straight (cost 0)
attempt_add(cost, r + dir[d][0], c + dir[d][1], d);
//previous dir (45 deg ccw) (cost 1)
add_nocheck(cost + 1, r, c, prev[d]);
//next dir (45 deg cw) (cost 1)
add_nocheck(cost + 1, r, c, next[d]);
}
if(node[0].empty() && node[1].empty()) //didn't reach end
ans = -1;
else
ans = cost;
//printf("%d adds\n", adds);
}
int main()
{
int i, j, tmp;
FILE *f = fopen("car.in", "r");
if(!f) return 1;
fscanf(f, "%d%d", &rows, &cols);
fscanf(f, "%d%d%d%d", &sr, &sc, &er, &ec);
sr--; sc--;
er--; ec--;
for(i = 0; i < rows; i++)
for(j = 0; j < cols; j++)
{
fscanf(f, "%d", &tmp);
bad[i][j] = tmp;
}
fclose(f);
f = fopen("car.out", "w");
if(!f) return 1;
go();
fprintf(f, "%d\n", ans);
fclose(f);
return 0;
}