Go to diff to previous submission
// // File: grasshop.cc // Author: cteam053 // // Created on October 27, 2012, 10:55 AM // #include <stdlib.h> #include <stdio.h> #include <cstdio> #include <cmath> #include <climits> #include <iostream> #include <list> using namespace std; int xmax, ymax; bool code(int x, int y, int& ret){ if(x <= 0 || y <= 0 || x > xmax || y > ymax) return false; ret = 1000*x + y; return true; } int main(int argc, char** argv) { int R, C, Gr, Gc, Lr, Lc; list<int> sData; list<int> len; int length = -1; int tmp, x, y, ret, request; while(1){ int ret = scanf("%d%d%d%d%d%d", &R, &C, &Gr, &Gc, &Lr, &Lc); if(ret != 6) return 0; xmax = R; ymax = C; code(Lr, Lc, request); code(Gr, Gc, ret); len.clear(); len.push_back(0); sData.clear(); sData.push_back(ret); while(!sData.empty()){ tmp = *(sData.begin()); sData.pop_front(); length = *(len.begin()); len.pop_front(); if(tmp == request) break; x = tmp / 1000; y = tmp % 1000; if(abs(x - Gr) > abs(Lr - Gr) + 4) continue; if(abs(y - Gc) > abs(Lc - Gc) + 4) continue; if(code(x-2, y-1, ret)){ sData.push_back(ret); len.push_back(length+1); } if(code(x-2, y+1, ret)){ len.push_back(length+1); sData.push_back(ret);} if(code(x-1, y+2, ret)){ len.push_back(length+1); sData.push_back(ret);} if(code(x+1, y+2, ret)){ len.push_back(length+1); sData.push_back(ret);} if(code(x+2, y+1, ret)){ len.push_back(length+1); sData.push_back(ret);} if(code(x+2, y-1, ret)){ len.push_back(length+1); sData.push_back(ret);} if(code(x+1, y-2, ret)){ len.push_back(length+1); sData.push_back(ret);} if(code(x-1, y-2, ret)){ len.push_back(length+1); sData.push_back(ret);} } if(length == 0) printf("impossible\n"); else printf("%d\n", length); } return (0); }