Go to diff to previous submission
#include <cstdio> #include <cstdlib> #include <iostream> using namespace std; bool ** bitmap; int R, C, Gr, Gc, Lr, Lc, steps, min_; bool rek(int x, int y, int steps) { //bitmap[x][y]; if (x == Lr && y == Lc) { if (min_ > steps) min_ = steps; return true; } bool ret = false; steps++; if ((R > C && steps > R/2+2) || (C >= R && steps > C/2+2)) return false; if (x+2 < R && y+1 < C && bitmap[x+2][y+1]) ret |= rek(x+2, y+1, steps); if (x+2 < R && y-1 >= 0 && bitmap[x+2][y-1]) ret |= rek(x+2, y-1, steps); if (x-2 >= 0 && y+1 < C && bitmap[x-2][y+1]) ret |= rek(x-2, y+1, steps); if (x-2 >= 0 && y-1 >= 0 && bitmap[x-2][y-1]) ret |= rek(x-2, y-1, steps); if (y+2 < C && x+1 < R && bitmap[x+1][y+2]) ret |= rek(x+1, y+2, steps); if (y+2 < C && x-1 >= 0 && bitmap[x-1][y+2]) ret |= rek(x-1, y+2, steps); if (y-2 >= 0 && x+1 < R && bitmap[x+1][y-2]) ret |= rek(x+1, y-2, steps); if (y-2 >= 0 && x-1 >= 0 && bitmap[x-1][y-2]) ret |= rek(x-1, y-2, steps); return ret; } int main() { while (cin >> R >> C >> Gr >> Gc >> Lr >> Lc) { bitmap = (bool **) malloc(sizeof(bool *) * R); for (int i=0; i<R; i++) { bitmap[i] = (bool *) malloc(sizeof(bool) * C); for (int j=0; j<C; j++) bitmap[i][j] = true; } Gr--; Gc--; Lr--; Lc--; min_ = R+C; if (!rek(Gr, Gc, 0)) cout << "impossible" << endl; else cout << min_ << endl; for (int i=0; i<R; i++) free(bitmap[i]); free(bitmap); } return 0; }
--- c4.s1004.cteam045.grasshop.cpp.0.grasshop.cpp +++ c4.s1007.cteam045.grasshop.cpp.0.grasshop.cpp @@ -18,5 +18,5 @@ bool ret = false; steps++; - if ((R > C && steps > R) || (C >= R && steps > C)) return false; + if ((R > C && steps > R/2+2) || (C >= R && steps > C/2+2)) return false; if (x+2 < R && y+1 < C && bitmap[x+2][y+1]) ret |= rek(x+2, y+1, steps); if (x+2 < R && y-1 >= 0 && bitmap[x+2][y-1]) ret |= rek(x+2, y-1, steps);