#define _USE_MATH_DEFINES
#include <fstream>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
#include <limits>
#define MAX_SIZE 501
#define INF 0x3f3f3f3f
#define ANGLE_INC M_PI_4
using namespace std;
struct Vector2D
{
Vector2D() :
x(0),
y(0)
{}
Vector2D(const short xx, const short yy) :
x(xx),
y(yy)
{}
bool operator == (const Vector2D& v) const
{
return (x == v.x && y == v.y);
}
bool operator != (const Vector2D& v) const
{
return (x != v.x || y != v.y);
}
short x, y;
};
Vector2D vDirections[] =
{
Vector2D(1,0),
Vector2D(1,1),
Vector2D(0,1),
Vector2D(-1,1),
Vector2D(-1,0),
Vector2D(-1,-1),
Vector2D(0,-1),
Vector2D(1,-1)
};
#define NUM_DIRECTIONS (sizeof(vDirections)/sizeof(Vector2D))
short explored[MAX_SIZE][MAX_SIZE];
struct Node
{
Node() :
bIsTraversable(true)
{
memset(dirCost, 0x3f, NUM_DIRECTIONS*sizeof(int));
}
operator bool() const
{
return bIsTraversable;
}
bool bIsTraversable;
int dirCost[NUM_DIRECTIONS];
};
typedef Vector2D Coord2D;
Node matDrivingField[MAX_SIZE][MAX_SIZE];
float GetUnitVectorAngle(const Vector2D& v1, const Vector2D& v2)
{
float magnitude = 2.0f;
const bool bAllNon0 = (v1.x && v1.y) && (v2.x && v2.y);
if (!bAllNon0)
{
const float magnitude1 = (v1.x && v1.y) ? 1.41421356f : 1.0f;
const float magnitude2 = (v2.x && v2.y) ? 1.41421356f : 1.0f;
magnitude = magnitude1 * magnitude2;
}
return acos( ((float)(v2.x*v1.x + v2.y*v1.y)) / (magnitude));
}
int GetCostFromDirDiff(const float fDirDiff)
{
return (int)(fDirDiff / ANGLE_INC);
}
void GetDestDir(const Coord2D& st, const Coord2D& end, Vector2D& v)
{
const int diffX = end.x-st.x;
switch (diffX)
{
case 0:
{
v.x = 0;
}; break;
default:
{
if (diffX <0)
{
v.x = -1;
}
else
{
v.x = 1;
}
}
}
const int diffY = end.y-st.y;
switch (diffY)
{
case 0:
{
v.y = 0;
}; break;
default:
{
if (diffY <0)
{
v.y = -1;
}
else
{
v.y = 1;
}
}
}
}
struct Pass
{
Pass() :
dir(0),
tentativeCost(0)
{}
Pass(const Coord2D& n, const short d, const int tc) :
dir(d),
tentativeCost(tc),
node(n)
{}
short dir;
int tentativeCost;
Coord2D node;
};
int BFS(const Coord2D& st, const Coord2D& end, const int n, const int m)
{
int cost = -1;
queue<Pass> Q;
for (int i=0; i<NUM_DIRECTIONS; ++i)
{
matDrivingField[st.x][st.y].dirCost[0] = 0;
const Coord2D pt(st.x + vDirections[i].x, st.y + vDirections[i].y);
if (pt.x >=0 && pt.x <n && pt.y >=0 && pt.y <n)
{
if (matDrivingField[pt.x][pt.y] == true)
{
matDrivingField[pt.x][pt.y].dirCost[0] = 0;
Vector2D vTC;
GetDestDir(st, pt, vTC);
Q.push(Pass(pt, i, GetCostFromDirDiff(GetUnitVectorAngle(vDirections[i], vTC))));
explored[pt.x][pt.y]++;
}
}
}
while (!Q.empty())
{
const Pass current = Q.front();
Q.pop();
if (current.node == end)
{
continue;
}
for (int i=0; i<NUM_DIRECTIONS; ++i)
{
const float fAngleDiff = GetUnitVectorAngle(vDirections[current.dir], vDirections[i]);
//if (fAngleDiff > 90)
// continue;
const Coord2D pt(current.node.x + vDirections[i].x, current.node.y + vDirections[i].y);
if (pt.x >=0 && pt.x <n && pt.y >=0 && pt.y <n)
{
if (matDrivingField[pt.x][pt.y] == true && pt != st)
{
if (matDrivingField[current.node.x][current.node.y].dirCost[0] == INF)
{
matDrivingField[current.node.x][current.node.y].dirCost[0] = matDrivingField[current.node.x][current.node.y].dirCost[0];
}
const int curCost = matDrivingField[current.node.x][current.node.y].dirCost[0] +
//matDrivingField[current.parent.x][current.parent.y].dirCost[current.dir] +
GetCostFromDirDiff(fAngleDiff);
if (matDrivingField[pt.x][pt.y].dirCost[0] > curCost)
{
matDrivingField[pt.x][pt.y].dirCost[0] = curCost;
Vector2D vTC;
GetDestDir(st, pt, vTC);
Q.push(Pass(pt, i, GetCostFromDirDiff(GetUnitVectorAngle(vDirections[i], vTC))));
//cout << "Processed " << pt.x << " " << pt.y << " " << curCost << "\n";
explored[pt.x][pt.y]++;
}
}
}
}
}
// get the lowest cost for teh final destination point
cost = matDrivingField[end.x][end.y].dirCost[0];
for (int i=1; i<NUM_DIRECTIONS; ++i)
{
cost = min(cost, matDrivingField[end.x][end.y].dirCost[i]);
}
if (cost < INF)
{
return cost;
}
return -1;
}
int main()
{
int n, m;
Coord2D st, end;
fstream fin("car.in", fstream::in);
fstream fout("car.out", fstream::out);
fin >> n >> m;
fin >> st.x >> st.y >> end.x >> end.y;
st.x--, st.y--;
end.x--, end.y--;
/*Vector2D v;
GetDestDir(Coord2D(1,1), Coord2D(-2,4), v);
cout << v.x << " " << v.y << "\n";
return 0;*/
if (st == end)
{
fout << 0 << "\n";
return 0;
}
/*cout << n << " " << m << "\n";
cout << st.x << " " << st.y << "\n";
cout << end.x << " " << end.y << "\n";*/
for (int i=0; i<n; ++i)
{
for (int j=0; j<m; ++j)
{
int x;
fin >> x;
if (x)
{
matDrivingField[i][j].bIsTraversable = false;
}
}
}
/*for (int i=0; i<n; ++i)
{
for (int j=0; j<m; ++j)
{
cout << !matDrivingField[i][j] << " ";
}
cout << "\n";
}*/
/*cout << 180*GetUnitVectorAngle(Vector2D(-1,1), Vector2D(1,0))/M_PI << endl;
for (int i=0; i< NUM_DIRECTIONS; ++i)
{
const float angleDiff = GetUnitVectorAngle(vDirections[i], Vector2D(1,0));
cout << GetCostFromDirDiff(angleDiff) << " ";
}
cout << "\n";*/
fout << BFS(st, end, n, m) << "\n";
/*for (int i=0; i<n; ++i)
{
for (int j=0; j<m; ++j)
{
cout << explored[i][j] << " ";
}
cout << "\n";
}*/
fin.close();
fout.close();
return 0;
}