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