grasshop.cpp
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define PB push_back
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define fi first
#define se second
#define SIZE(s) (int) (s).size()
#define INF 987654321
#define ll long long
//----------------------
#define MAX 147
int X,Y;
int beginY, beginX;
int endX, endY;
int D[MAX][MAX];
int diry[8] = {1,2,2,1,-1,-2,-2,-1};
int dirx[8] = {2,1,-1,-2,-2,-1,1,2};
bool ok(int y, int x)
{
return (y >= 0 && y < Y) && (x >= 0 && x < X);
}
int bfs()
{
FOR(i,0,Y-1) FOR(j,0,X-1) D[i][j] = 0;
queue< PII > Q;
Q.push(MP(beginY,beginX));
while(!Q.empty())
{
PII front = Q.front();
Q.pop();
int d = D[front.fi][front.se];
if (front.fi == endY && front.se == endX)
return d;
FOR(dir,0,7)
{
int y = front.fi + diry[dir];
int x = front.se + dirx[dir];
if (ok(y,x))
{
D[y][x] = d+1;
Q.push(MP(y,x));
}
}
}
return -1;
}
int main()
{
while(scanf("%d %d %d %d %d %d",&Y,&X,&beginY,&beginX,&endY,&endX) == 6)
{
beginX--;
beginY--;
endX--;
endY--;
int res = bfs();
if (res==-1)
printf("impossible\n");
else printf("%d\n",res);
}
return 0;
}