grasshop.cpp

#include <stdio.h>
#include <stdlib.h>
 
#define MAXW 200
#define MAXH 200
 
typedef struct ITEM
{
	int x;
	int y;
 
	ITEM() {}
	ITEM(int x, int y): x(x), y(y) {}
}
ITEM;
 
ITEM Move[8] =
{
	(ITEM) {2, 1},
	(ITEM) {-2, 1},
	(ITEM) {2, -1},
	(ITEM) {-2, -1},
	(ITEM) {1, 2},
	(ITEM) {-1, 2},
	(ITEM) {1, -2},
	(ITEM) {-1, -2}
};
 
int Dist[MAXW][MAXH];
ITEM Queue[MAXW * MAXH];
int QueueBeg;
int QueueEnd;
 
int Inside(int x, int y, int w, int h)
{
	return ((x >= 0) && (x < w) && (y >= 0) && (y < h));
}
 
void Print(int w, int h)
{
	for(int y = 0; y < h; y++)
	{
		for(int x = 0; x < w; x++)
		{
			printf("%3d", Dist[x][y]);
		}
 
		printf("\n");
	}
}
 
int main()
{
	int w, h, x1, y1, x2, y2;
	while(scanf("%d%d%d%d%d%d", &w, &h, &x1, &y1, &x2, &y2) > 0)
	{
		x1--;
		y1--;
		x2--;
		y2--;
 
		for(int i = 0; i < w; i++)
		{
			for(int j = 0; j < h; j++)
			{
				Dist[i][j] = -1;
			}
		}
 
		QueueBeg = 0;
		QueueEnd = 0;
 
		Dist[x1][y1] = 0;
		Queue[QueueEnd++] = ITEM(x1, y1);
 
		while(QueueBeg < QueueEnd)
		{
			ITEM cur = Queue[QueueBeg++];
 
			for(int i = 0; i < 8; i++)
			{
				int x = cur.x + Move[i].x;
				int y = cur.y + Move[i].y;
				int d = Dist[cur.x][cur.y] + 1;
 
				if(Inside(x, y, w, h))
				{
					if((x == x2) && (y == y2))
					{
						printf("%d\n", d);
						goto OK;
					}
 
					if(Dist[x][y] == -1)
					{
						Queue[QueueEnd++] = ITEM(x, y);
						Dist[x][y] = d;
					}
				}
			}
		}
 
		printf("impossible\n");
		OK:;
 
		//Print(w, h);
	}
 
	return 0;
}