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> #include <set> using namespace std; int xmax, ymax; int obs[101][101]; bool code(int x, int y, int& ret){ if(x <= 0 || y <= 0 || x > xmax || y > ymax) return false; ret = 1000*x + y; if(obs[x][y] == 1){ return false; } obs[x][y] = 1; 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); for(int i = 0; i <= 100; i++) for(int j = 0; j <= 100; j++) obs[i][j] = 0; obs[Gr][Gc] = 1; 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(max(abs(x-Lr), abs(y-Lc)) > 4){ //printf("x=%d y=%d\n", x, y); if((Lr-x) > 0){ if((Lc-y) > 0){ 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);} }else{ 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);} } }else{ if((Lc-y) > 0){ 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);} }else{ if(code(x-2, y-1, ret)){ sData.push_back(ret); len.push_back(length+1); } if(code(x-1, y-2, ret)){ len.push_back(length+1); sData.push_back(ret);} } } }else{ 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); }
--- c4.s760.cteam053.grasshop.cpp.0.grasshop.cpp +++ c4.s984.cteam053.grasshop.cpp.0.grasshop.cpp @@ -13,13 +13,20 @@ #include <iostream> #include <list> +#include <set> using namespace std; int xmax, ymax; +int obs[101][101]; bool code(int x, int y, int& ret){ if(x <= 0 || y <= 0 || x > xmax || y > ymax) return false; + ret = 1000*x + y; + if(obs[x][y] == 1){ + return false; + } + obs[x][y] = 1; return true; } @@ -33,4 +40,5 @@ list<int> sData; list<int> len; + int length = -1; int tmp, x, y, ret, request; @@ -50,4 +58,8 @@ sData.clear(); sData.push_back(ret); + for(int i = 0; i <= 100; i++) + for(int j = 0; j <= 100; j++) + obs[i][j] = 0; + obs[Gr][Gc] = 1; while(!sData.empty()){ tmp = *(sData.begin()); @@ -60,41 +73,80 @@ y = tmp % 1000; - if(abs(x - Gr) > abs(Lr - Gr) + 4) - continue; - if(abs(y - Gc) > abs(Lc - Gc) + 4) - continue; + if(max(abs(x-Lr), abs(y-Lc)) > 4){ + //printf("x=%d y=%d\n", x, y); + if((Lr-x) > 0){ + if((Lc-y) > 0){ + if(code(x+1, y+2, ret)){ + len.push_back(length+1); + sData.push_back(ret);} - 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);} + }else{ + 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);} + } + }else{ + if((Lc-y) > 0){ + 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);} + }else{ + if(code(x-2, y-1, ret)){ + sData.push_back(ret); + len.push_back(length+1); + } + if(code(x-1, y-2, ret)){ + len.push_back(length+1); + sData.push_back(ret);} + } + + } + + }else{ - if(code(x+1, y+2, ret)){ - len.push_back(length+1); - sData.push_back(ret);} + 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-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(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)