Source code for submission s735

grasshop.cpp

  1. // 
  2. // File:   grasshop.cc
  3. // Author: cteam053
  4. //
  5. // Created on October 27, 2012, 10:55 AM
  6. //
  7.  
  8. #include <stdlib.h>
  9. #include <stdio.h>
  10. #include <cstdio>
  11. #include <cmath>
  12. #include <climits>
  13. #include <iostream>
  14. #include <list>
  15.  
  16. using namespace std;
  17.  
  18. int xmax, ymax;
  19.  
  20. bool code(int x, int y, int& ret){
  21.     if(x <= 0 || y <= 0 || x > xmax || y > ymax)
  22.         return false;
  23.     ret = 1000*x + y;
  24.     return true;
  25. }
  26.  
  27.  
  28.  
  29.  
  30. int main(int argc, char** argv) {
  31.  
  32.     int R, C, Gr, Gc, Lr, Lc;
  33.     list<int> sData;
  34.     list<int> len;
  35.     int length = -1;
  36.     int tmp, x, y, ret, request;
  37.  
  38.     while(1){
  39.         int ret = scanf("%d%d%d%d%d%d", &R, &C, &Gr, &Gc, &Lr, &Lc);
  40.         if(ret != 6)
  41.             return 0;
  42.  
  43.         xmax = R;
  44.         ymax = C;
  45.         code(Lr, Lc, request);
  46.  
  47.         code(Gr, Gc, ret);
  48.         len.clear();
  49.         len.push_back(0);
  50.         sData.clear();
  51.         sData.push_back(ret);
  52.         while(!sData.empty()){
  53.             tmp = *(sData.begin());
  54.             sData.pop_front();
  55.             length = *(len.begin());
  56.             len.pop_front();
  57.             if(tmp == request)
  58.                 break;
  59.             x = tmp / 1000;
  60.             y = tmp % 1000;
  61.  
  62.             if(code(x-2, y-1, ret)){
  63.                 sData.push_back(ret);
  64.                 len.push_back(length+1);
  65.             }
  66.  
  67.             if(code(x-2, y+1, ret)){
  68.                 len.push_back(length+1);
  69.                 sData.push_back(ret);}
  70.  
  71.             if(code(x-1, y+2, ret)){
  72.                 len.push_back(length+1);
  73.                 sData.push_back(ret);}
  74.  
  75.             if(code(x+1, y+2, ret)){
  76.                 len.push_back(length+1);
  77.                 sData.push_back(ret);}
  78.  
  79.             if(code(x+2, y+1, ret)){
  80.                 len.push_back(length+1);
  81.                 sData.push_back(ret);}
  82.  
  83.             if(code(x+2, y-1, ret)){
  84.                 len.push_back(length+1);
  85.                 sData.push_back(ret);}
  86.  
  87.             if(code(x+1, y-2, ret)){
  88.                 len.push_back(length+1);
  89.                 sData.push_back(ret);}
  90.  
  91.             if(code(x-1, y-2, ret)){
  92.                 len.push_back(length+1);
  93.                 sData.push_back(ret);}
  94.         }
  95.         if(length == 0)
  96.             printf("impossible\n");
  97.         else
  98.             printf("%d\n", length);
  99.     }
  100.  
  101.  
  102.  
  103.     return (0);
  104. }
  105.  
  106.