grasshop.cpp
#include <iostream>
#include <cstdio>
#include <queue>
#include <set>
#define getc() getc(stdin)
typedef unsigned int uint;
using namespace std;
struct pos {
int r;
int c;
int jumps;
};
int main()
{
int rMod[8] = {2,2,1,-1,-2,-2,-1,1};
int cMod[8] = {-1,1,2,2,1,-1,-2,-2};
int R = 0, C = 0, GR = 0, GC = 0, LR = 0, LC = 0;
while (scanf("%d%d%d%d%d%d", &R, &C, &GR, &GC, &LR, &LC) == 6) {
queue<pos> q;
pos start;
set<pair<int, int> > positions;
start.c = GC;
start.r = GR;
start.jumps = 0;
q.push(start);
positions.insert(make_pair(GC, GR));
while (!q.empty()) {
pos oldPos = q.front();
q.pop();
if (oldPos.c == LC && oldPos.r == LR) {
printf("%d\n", oldPos.jumps);
break;
}
oldPos.jumps++;
for (int i = 0; i < 8; i++) {
if (oldPos.r + rMod[i] <= R && oldPos.r + rMod[i] >= 1 &&
oldPos.c + cMod[i] <= C && oldPos.c + cMod[i] >= 1) {
pos newPos;
newPos.jumps = oldPos.jumps;
newPos.r = oldPos.r + rMod[i];
newPos.c = oldPos.c + cMod[i];
if (positions.insert(make_pair(newPos.r, newPos.c)).second)
{
q.push(newPos);
}
}
}
}
if (q.empty()) {
printf("impossible\n");
}
}
// cout << "Hello World!" << endl;
return 0;
}