grasshop.cpp
#include <stdio.h>
#include <string.h>
#include <deque>
struct Point {
int x, y;
Point(int x_, int y_) : x(x_), y(y_) {}
};
int r, c, gr, gc, lr, lc;
std::deque<Point> q;
void addPoint(int x, int y, bool* seen) {
if (!seen[y * c + x] && x >= 0 && y >= 0 && x < c && y < r) {
q.push_back(Point(x, y));
seen[y * c + x] = true;
}
}
int main() {
while (scanf("%d %d %d %d %d %d\n", &r, &c, &gr, &gc, &lr, &lc) != EOF) {
--gr;
--gc;
--lr;
--lc;
bool seen[r * c];
memset(seen, 0, r * c);
q.push_back(Point(gc, gr));
seen[gr * c + gc] = true;
q.push_back(Point(-5, -5));
int count = 0;
while (q.size() > 1) {
Point p = q.front();
q.pop_front();
int x = p.x;
int y = p.y;
if (x == lc && y == lr) {
printf("%d\n", count);
goto clearLabel;
} else if (x == -5) {
++count;
q.push_back(Point(-5, -5));
continue;
}
addPoint(x - 2, y - 1, seen);
addPoint(x - 1, y - 2, seen);
addPoint(x + 1, y - 2, seen);
addPoint(x + 2, y - 1, seen);
addPoint(x + 2, y + 1, seen);
addPoint(x + 1, y + 2, seen);
addPoint(x - 1, y + 2, seen);
addPoint(x - 2, y + 1, seen);
}
printf("impossible\n");
clearLabel:
q.clear();
}
return 0;
}