grasshopper.cpp

#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
 
vector<vector<int> > g;
int r, c, gr, gc, lr, lc;
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
 
bool valid(int x, int y) {
	return x >= 0 && x < r && y >= 0 && y < c;
}
 
int bfs(int start, int target) {
	vector<bool> mark(r * c, false);
	queue<pair<int, int> > q;
	q.push(make_pair(start, 0));
	mark[start] = true;
	while(not q.empty()) {
		int x = q.front().first;
		int d = q.front().second;
		q.pop();
		if (x == target) {
			return d;
		}
		for (int i = 0; i < (int) g[x].size(); ++i) {
			int y = g[x][i];
			if (not mark[y]) {
				mark[y] = true;
				q.push(make_pair(y, d + 1));
			}
		}
	}
	return -1;
}
 
int main() {
	while(scanf("%d %d", &r, &c) == 2) {
		scanf("%d %d %d %d", &gr, &gc, &lr, &lc);
		--gr; --gc; --lr; --lc;
		g.assign(r * c, vector<int> ());
		for (int i = 0; i < r; ++i) {
			for (int j = 0; j < c; ++j) {
				for (int k = 0; k < 8; ++k) {
					int x = i + dx[k];
					int y = j + dy[k];
					if (valid(x, y)) {
						fflush(stdout);
						g[i * c + j].push_back(x * c + y);
					}
				}
			}
		}
		int d = bfs(gr * c + gc, lr * c + lc);
		if (d < 0) printf("impossible\n");
		else printf("%d\n", d);
	}
	return 0;
}