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