grasshop.cpp

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
 
using namespace std;
 
struct Point {
	int a;
	int b;
};
 
queue <Point> trace;
int grid[200][200];
int a, b, a1, b1, a2, b2;
 
bool push (Point next) {
	Point cur = trace.front();
	if (next.a >= 0 && next.a < a && next.b >= 0 && next.b < b) {
		if (grid[cur.a][cur.b] + 1 < grid[next.a][next.b]) { 
			trace.push (next);
			grid[next.a][next.b] = grid[cur.a][cur.b] + 1;
			if (next.a == a2 && next.b == b2)
				return true;
		}
	}
	return false;
}
 
int main() {
	while (scanf ("%d%d%d%d%d%d", &a, &b, &a1, &b1, &a2, &b2) == 6) {
		for (int i = 0; i < 200; i++)
			for (int j = 0; j < 200; j++)
				grid[i][j] = 1000000000;
 
		Point start;
		start.a = a1;
		start.b = b1;
		grid[a1][b1] = 0;
		trace.push (start);
		while (!trace.empty()) {
			Point cur = trace.front();
			Point next;
			next.a = cur.a - 2;
			next.b = cur.b - 1;
			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
			next.a = cur.a - 2;
			next.b = cur.b + 1;
			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
			next.a = cur.a + 2;
			next.b = cur.b - 1;
			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
			next.a = cur.a + 2;
			next.b = cur.b + 1;
			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
			next.a = cur.a - 1;
			next.b = cur.b - 2;
			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
			next.a = cur.a - 1;
			next.b = cur.b + 2;
			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
			next.a = cur.a + 1;
			next.b = cur.b - 2;
			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
			next.a = cur.a + 1;
			next.b = cur.b + 2;
			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
			trace.pop();
		}
		printf ("impossible\n");	
		next:;
		while (!trace.empty()) trace.pop();
	}
	return 0;
}