Source code for submission s984

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, x, y, ret, request;
  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.  
  55.         code(Gr, Gc, ret);
  56.         len.clear();
  57.         len.push_back(0);
  58.         sData.clear();
  59.         sData.push_back(ret);
  60.         for(int i = 0; i <= 100; i++)
  61.             for(int j = 0; j <= 100; j++)
  62.                 obs[i][j] = 0;
  63.         obs[Gr][Gc] = 1;
  64.         while(!sData.empty()){
  65.             tmp = *(sData.begin());
  66.  
  67.             sData.pop_front();
  68.             length = *(len.begin());
  69.             len.pop_front();
  70.             if(tmp == request)
  71.                 break;
  72.             x = tmp / 1000;
  73.             y = tmp % 1000;
  74.  
  75.             if(max(abs(x-Lr), abs(y-Lc)) > 4){
  76.                 //printf("x=%d y=%d\n", x, y);
  77.                 if((Lr-x) > 0){
  78.                     if((Lc-y) > 0){
  79.                         if(code(x+1, y+2, 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.                     }else{
  87.                         if(code(x+2, y-1, 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.                 }else{
  96.                     if((Lc-y) > 0){
  97.                         if(code(x-2, y+1, ret)){
  98.                             len.push_back(length+1);
  99.                             sData.push_back(ret);}
  100.  
  101.                         if(code(x-1, y+2, ret)){
  102.                             len.push_back(length+1);
  103.                             sData.push_back(ret);}
  104.                     }else{
  105.                         if(code(x-2, y-1, ret)){
  106.                             sData.push_back(ret);
  107.                             len.push_back(length+1);
  108.                         }
  109.                         if(code(x-1, y-2, ret)){
  110.                             len.push_back(length+1);
  111.                             sData.push_back(ret);}
  112.                         }
  113.  
  114.                 }
  115.  
  116.             }else{
  117.  
  118.                 if(code(x-2, y-1, ret)){
  119.                     sData.push_back(ret);
  120.                     len.push_back(length+1);
  121.                 }
  122.  
  123.                 if(code(x-2, y+1, ret)){
  124.                     len.push_back(length+1);
  125.                     sData.push_back(ret);}
  126.  
  127.                 if(code(x-1, y+2, ret)){
  128.                     len.push_back(length+1);
  129.                     sData.push_back(ret);}
  130.  
  131.                 if(code(x+1, y+2, ret)){
  132.                     len.push_back(length+1);
  133.                     sData.push_back(ret);}
  134.  
  135.                 if(code(x+2, y+1, ret)){
  136.                     len.push_back(length+1);
  137.                     sData.push_back(ret);}
  138.  
  139.                 if(code(x+2, y-1, ret)){
  140.                     len.push_back(length+1);
  141.                     sData.push_back(ret);}
  142.  
  143.                 if(code(x+1, y-2, ret)){
  144.                     len.push_back(length+1);
  145.                     sData.push_back(ret);}
  146.  
  147.                 if(code(x-1, y-2, ret)){
  148.                     len.push_back(length+1);
  149.                     sData.push_back(ret);}
  150.             }
  151.         }
  152.         if(length == 0)
  153.             printf("impossible\n");
  154.         else
  155.             printf("%d\n", length);
  156.     }
  157.  
  158.  
  159.  
  160.     return (0);
  161. }
  162.  
  163.  

Diff to submission s760

grasshop.cpp

--- 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)