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; 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; }
--- c4.s689.cteam093.grasshop.cpp.0.grasshop.cpp +++ c4.s716.cteam093.grasshop.cpp.0.grasshop.cpp @@ -24,28 +24,26 @@ pos start; set<pair<int, int> > positions; - start.c = GC; start.r = GR; + start.c = GC; start.jumps = 0; q.push(start); - positions.insert(make_pair(GR, GC)); - - while (!q.empty()) { - + positions.insert(make_pair(start.r, start.c)); + bool done = false; + while (!q.empty() && !done) { 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]; + 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) { @@ -56,9 +54,8 @@ } - if (q.empty()) { + if (!done) { printf("impossible\n"); } } - // cout << "Hello World!" << endl; return 0; }