grasshop.cpp

#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
int R, C;
 
typedef struct {
	int x, y;
} coord;
 
// We could not remember struct constructor syntax... :-/
coord makecoord(int x, int y) {
	coord temp;
	temp.x = x;
	temp.y = y;
	return temp;
}
 
inline bool is_inside(int x, int y) {
	return (x >= 0 && y >= 0 && x < R && y < C);
}
 
inline bool is_inside(coord c) {
	return is_inside(c.x, c.y);
}
 
vector<coord> get_neighbours(coord c) {
	vector<coord> temp;
	int x = c.x;
	int y = c.y;
	if (is_inside(x+2,y-1)) { temp.push_back(makecoord(x+2, y-1)); }
	if (is_inside(x+2,y+1)) { temp.push_back(makecoord(x+2, y+1)); }
	if (is_inside(x-2,y-1)) { temp.push_back(makecoord(x-2, y-1)); }
	if (is_inside(x-2,y+1)) { temp.push_back(makecoord(x-2, y+1)); }
	if (is_inside(x-1,y+2)) { temp.push_back(makecoord(x-1, y+2)); }
	if (is_inside(x+1,y+2)) { temp.push_back(makecoord(x+1, y+2)); }
	if (is_inside(x-1,y-2)) { temp.push_back(makecoord(x-1, y-2)); }
	if (is_inside(x+1,y-2)) { temp.push_back(makecoord(x+1, y-2)); }
	return temp;
}
 
inline bool is_unvisited(coord c, const vector<vector<int> > &map) {
	return map[c.x][c.y] == 0;
}
 
int main() {
	int Gr, Gc, Lr, Lc;
	while (scanf("%d %d %d %d %d %d", &R, &C, &Gr, &Gc, &Lr, &Lc) == 6) {
		if (Gr == Lr && Gc == Lc) { printf("0\n"); continue; }
		vector<vector<int> > field(R);
		for (int i = 0; i < R; i++) {
			field[i].resize(C);
		}
		queue<coord> q;
		coord current;
		q.push(makecoord(Gr-1, Gc-1));
		int level = 1;
		size_t remaining = 1;
		while(!q.empty()) {
			remaining--;
			if (remaining == 0) { level++; remaining = q.size(); }
			current = q.front();
			q.pop();
			if (current.x == Lr-1 && current.y == Lc-1) {
				break;
			}
			vector<coord> neig = get_neighbours(current);
			for (size_t i = 0; i < neig.size(); i++) {
				if (is_unvisited(neig[i], field)) {
					field[neig[i].x][neig[i].y] = level;
					q.push(neig[i]);
				}
			}
		}
		if (field[Lr-1][Lc-1] != 0) {
			printf("%d\n", field[Lr-1][Lc-1]-1);
		} else {
			printf("impossible\n");
		}
	}
	return 0;
}