Source code for submission s1120

Go to diff to previous submission

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. #include <set>
  16.  
  17. using namespace std;
  18.  
  19. int xmax, ymax;
  20. int obs[101][101];
  21.  
  22. bool code(int x, int y, int& ret){
  23.     if(x <= 0 || y <= 0 || x > xmax || y > ymax)
  24.         return false;
  25.  
  26.     ret = 1000*x + y;
  27.     if(obs[x][y] == 1){
  28.         return false;
  29.     }
  30.     obs[x][y] = 1;
  31.     return true;
  32. }
  33.  
  34.  
  35.  
  36.  
  37. int main(int argc, char** argv) {
  38.  
  39.     int R, C, Gr, Gc, Lr, Lc;
  40.     list<int> sData;
  41.     list<int> len;
  42.  
  43.     int length = -1;
  44.     int tmp = 0, x, y, ret, request = 0;
  45.  
  46.     while(1){
  47.         int ret = scanf("%d%d%d%d%d%d", &R, &C, &Gr, &Gc, &Lr, &Lc);
  48.         if(ret != 6)
  49.             return 0;
  50.  
  51.         xmax = R;
  52.         ymax = C;
  53.         code(Lr, Lc, request);
  54.         obs[Lr][Lc] = 0;
  55.  
  56.         code(Gr, Gc, ret);
  57.         len.clear();
  58.         len.push_back(0);
  59.         sData.clear();
  60.         sData.push_back(ret);
  61.         for(int i = 0; i <= 100; i++)
  62.             for(int j = 0; j <= 100; j++)
  63.                 obs[i][j] = 0;
  64.         obs[Gr][Gc] = 1;
  65.         while(!sData.empty()){
  66.             tmp = *(sData.begin());
  67.  
  68.             sData.pop_front();
  69.             length = *(len.begin());
  70.             len.pop_front();
  71.             if(tmp == request)
  72.                 break;
  73.             x = tmp / 1000;
  74.             y = tmp % 1000;
  75.  
  76.             if(max(abs(x-Lr), abs(y-Lc)) > 6){
  77.                 //printf("x=%d y=%d\n", x, y);
  78.                 if((Lr-x) >= 0){
  79.                     if((Lc-y) >= 0){
  80.                         if(code(x+1, y+2, ret)){
  81.                             len.push_back(length+1);
  82.                             sData.push_back(ret);}
  83.  
  84.                         if(code(x+2, y+1, ret)){
  85.                             len.push_back(length+1);
  86.                             sData.push_back(ret);}
  87.                     }if((Lc-y) <= 0){
  88.                         if(code(x+2, y-1, ret)){
  89.                             len.push_back(length+1);
  90.                             sData.push_back(ret);}
  91.  
  92.                         if(code(x+1, y-2, ret)){
  93.                             len.push_back(length+1);
  94.                             sData.push_back(ret);}
  95.                     }
  96.                 }if((Lr-x) <= 0){
  97.                     if((Lc-y) >= 0){
  98.                         if(code(x-2, y+1, ret)){
  99.                             len.push_back(length+1);
  100.                             sData.push_back(ret);}
  101.  
  102.                         if(code(x-1, y+2, ret)){
  103.                             len.push_back(length+1);
  104.                             sData.push_back(ret);}
  105.                     }if((Lc-y) <= 0){
  106.                         if(code(x-2, y-1, ret)){
  107.                             sData.push_back(ret);
  108.                             len.push_back(length+1);
  109.                         }
  110.                         if(code(x-1, y-2, ret)){
  111.                             len.push_back(length+1);
  112.                             sData.push_back(ret);}
  113.                         }
  114.  
  115.                 }
  116.  
  117.             }else{
  118.  
  119.                 if(code(x-2, y-1, ret)){
  120.                     sData.push_back(ret);
  121.                     len.push_back(length+1);
  122.                 }
  123.  
  124.                 if(code(x-2, y+1, ret)){
  125.                     len.push_back(length+1);
  126.                     sData.push_back(ret);}
  127.  
  128.                 if(code(x-1, y+2, ret)){
  129.                     len.push_back(length+1);
  130.                     sData.push_back(ret);}
  131.  
  132.                 if(code(x+1, y+2, ret)){
  133.                     len.push_back(length+1);
  134.                     sData.push_back(ret);}
  135.  
  136.                 if(code(x+2, y+1, ret)){
  137.                     len.push_back(length+1);
  138.                     sData.push_back(ret);}
  139.  
  140.                 if(code(x+2, y-1, ret)){
  141.                     len.push_back(length+1);
  142.                     sData.push_back(ret);}
  143.  
  144.                 if(code(x+1, y-2, ret)){
  145.                     len.push_back(length+1);
  146.                     sData.push_back(ret);}
  147.  
  148.                 if(code(x-1, y-2, ret)){
  149.                     len.push_back(length+1);
  150.                     sData.push_back(ret);}
  151.             }
  152.         }
  153.         if(length == 0 || tmp != request)
  154.             printf("impossible\n");
  155.         else
  156.             printf("%d\n", length);
  157.     }
  158.  
  159.  
  160.  
  161.     return (0);
  162. }
  163.  
  164.  
  165.  
  166.  

Diff to submission s1115

grasshop.cpp

--- c4.s1115.cteam053.grasshop.cpp.0.grasshop.cpp
+++ c4.s1120.cteam053.grasshop.cpp.0.grasshop.cpp
@@ -42,5 +42,5 @@
     
     int length = -1;
-    int tmp, x, y, ret, request;
+    int tmp = 0, x, y, ret, request = 0;
         
     while(1){
@@ -52,4 +52,5 @@
         ymax = C;
         code(Lr, Lc, request);
+        obs[Lr][Lc] = 0;
 
         code(Gr, Gc, ret);