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