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