Go to diff to previous submission
#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) != EOF) { queue<pos> q; pos start; set<pair<int, int> > positions; start.r = GR; start.c = GC; start.jumps = 0; if (GR == LR && GC == LC) { printf("0\n"); continue; } q.push(start); positions.insert(make_pair(start.r, start.c)); bool done = false; while (!q.empty() && !done) { pos oldPos = q.front(); q.pop(); oldPos.jumps++; for (int i = 0; i < 8; i++) { pos newPos; newPos.jumps = oldPos.jumps; newPos.r = oldPos.r + rMod[i]; newPos.c = oldPos.c + cMod[i]; if (newPos.c == LC && newPos.r == LR) { printf("%d\n", newPos.jumps); done = true; break; } if (newPos.r <= R && newPos.r >= 1 && newPos.c <= C && newPos.c >= 1) { if (positions.insert(make_pair(newPos.r, newPos.c)).second) { q.push(newPos); } } } } if (!done) { printf("impossible\n"); } } return 0; }