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)