Source code for submission s1172

Go to diff to previous submission

grasshop.cpp

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. using namespace std;
  6.  
  7. struct Node {
  8. int r;
  9. int c;
  10. int value;
  11. };
  12.  
  13. bool canGo(int GR, int GC, int R, int C)
  14. {
  15. bool can = false;
  16. if(GR >= 1 && GR <= R && GC >= 1 && GC <= C)
  17. can = true;
  18. else
  19. can = false;
  20.  
  21. return can;
  22. }
  23. bool isPosib(Node * end, int i, int R, int C)
  24. {
  25. if( !canGo(end[i].r ,end[i].c,R,C) )
  26. return false;
  27.  
  28. if( i == 0 || i == 2 || i == 3 || i == 7 || i == 12 || i == 16 || i == 17 || i == 19 )
  29. return true;
  30. else
  31. {
  32. if( i == 1 )
  33. return ( isPosib(end, 3, R, C) || isPosib(end, 7, R, C) );
  34. else if( i == 4 )
  35. return ( isPosib(end, 12, R, C) || isPosib(end, 2, R, C) );
  36. else if( i == 6 )
  37. return ( isPosib(end, 16, R, C) || isPosib(end, 0, R, C) );
  38. else if( i == 8 )
  39. return ( isPosib(end, 17, R, C) || isPosib(end, 0, R, C) );
  40. else if( i == 11 )
  41. return ( isPosib(end, 19, R, C) || isPosib(end, 2, R, C) );
  42. else if( i == 13 )
  43. return ( isPosib(end, 19, R, C) || isPosib(end, 3, R, C) );
  44. else if( i == 15 )
  45. return ( isPosib(end, 17, R, C) || isPosib(end, 7, R, C) );
  46. else if( i == 18 )
  47. return ( isPosib(end, 12, R, C) || isPosib(end, 16, R, C) );
  48. else if( i == 5 )
  49. return ( isPosib(end, 8, R, C) || isPosib(end, 11, R, C) );
  50. else if( i == 9 )
  51. return ( isPosib(end, 1, R, C) || isPosib(end, 18, R, C) );
  52. else if( i == 10 )
  53. return ( isPosib(end, 1, R, C) || isPosib(end, 18, R, C) );
  54. else if( i == 14 )
  55. return ( isPosib(end, 8, R, C) || isPosib(end, 11, R, C) );
  56.  
  57. }
  58. return false;
  59. }
  60.  
  61. int isIn(int r, int c, Node* end,int Rgride, int Cgride, int LR, int LC)
  62. {
  63. if(LR == r && LC == c)
  64. return 0;
  65. for(int i = 0; i < 20; i++)
  66. {
  67. if( end[i].r == r && end[i].c == c )
  68. {
  69. if( canGo(end[i].r ,end[i].c,Rgride,Cgride) )
  70. {
  71. if( isPosib(end,i,Rgride,Cgride) )
  72. return end[i].value;
  73. else
  74. return -1;
  75. }
  76. else
  77. return -1;
  78. }
  79. }
  80. return -1;
  81. }
  82.  
  83. bool isMax(int a, int b){
  84. if(a > b)
  85. return true;
  86. else
  87. return false;
  88. }
  89.  
  90. void createEnd( Node* end , int lr, int lc )
  91. {
  92. end[0].r = lr - 2;
  93. end[0].c = lc - 1;
  94. end[0].value = 1;
  95.  
  96. end[1].r = lr - 2;
  97. end[1].c = lc - 0;
  98. end[1].value = 2;
  99.  
  100. end[2].r = lr - 2;
  101. end[2].c = lc + 1;
  102. end[2].value = 1;
  103. //---
  104. end[3].r = lr - 1;
  105. end[3].c = lc - 2;
  106. end[3].value = 1;
  107.  
  108. end[4].r = lr - 1;
  109. end[4].c = lc - 1;
  110. end[4].value = 2;
  111.  
  112. end[5].r = lr - 1;
  113. end[5].c = lc - 0;
  114. end[5].value = 3;
  115.  
  116. end[6].r = lr - 1;
  117. end[6].c = lc + 1;
  118. end[6].value = 2;
  119.  
  120. end[7].r = lr - 1;
  121. end[7].c = lc + 2;
  122. end[7].value = 1;
  123. //---
  124. end[8].r = lr + 0;
  125. end[8].c = lc - 2;
  126. end[8].value = 2;
  127.  
  128. end[9].r = lr + 0;
  129. end[9].c = lc - 1;
  130. end[9].value = 3;
  131.  
  132. end[10].r = lr + 0;
  133. end[10].c = lc + 1;
  134. end[10].value = 3;
  135.  
  136. end[11].r = lr + 0;
  137. end[11].c = lc + 2;
  138. end[11].value = 2;
  139. //---
  140. end[12].r = lr + 1;
  141. end[12].c = lc - 2;
  142. end[12].value = 1;
  143.  
  144. end[13].r = lr + 1;
  145. end[13].c = lc - 1;
  146. end[13].value = 2;
  147.  
  148. end[14].r = lr + 1;
  149. end[14].c = lc - 0;
  150. end[14].value = 3;
  151.  
  152. end[15].r = lr + 1;
  153. end[15].c = lc + 1;
  154. end[15].value = 2;
  155.  
  156. end[16].r = lr + 1;
  157. end[16].c = lc + 2;
  158. end[16].value = 1;
  159. //---
  160.  
  161. end[17].r = lr + 2;
  162. end[17].c = lc - 1;
  163. end[17].value = 1;
  164.  
  165. end[18].r = lr + 2;
  166. end[18].c = lc - 0;
  167. end[18].value = 2;
  168.  
  169. end[19].r = lr + 2;
  170. end[19].c = lc + 1;
  171. end[19].value = 1;
  172. }
  173.  
  174. void setBoolean(int GR, int GC,int LR,int LC, bool&right, bool&top, bool&convert )
  175. {
  176. if(GR < LR) top = false;
  177. else top = true;
  178. if(GC < LC) right = true;
  179. else right = false;
  180.  
  181. if( top && right ) // nahoru doprava
  182. convert = isMax( GR-LR, GC-LC ); // true: nahoru 2x, doprava 1x; false: nahoru 1x, doprava 2x;
  183. else if( top && !right ) // nahoru doleva
  184. convert = isMax( GR-LR, GC-LC ); // true: nahoru 2x, doleva 1x; false: nahoru 1x, doleva 2x;
  185. else if( !top && right ) // dolu doprava
  186. convert = isMax( GR-LR, GC-LC ); // true: dolu 2x, doprava 1x; false: dolu 1x, doprava 2x;
  187. else if( !top && !right ) // dolu doleva
  188. convert = isMax( GR-LR, GC-LC ); // true: dolu 2x, doleva 1x; false: dolu 1x, doleva 2x;
  189. }
  190.  
  191. int main(void) {
  192. int R,C,GR,GC,LR,LC;
  193. int pomGR,pomGC;
  194. int inR, inC;
  195. bool right,top,convert,posible;
  196. int pomVal;
  197. int counter = 0;
  198. Node* end;
  199. while(scanf("%d %d %d %d %d %d",&R,&C,&GR,&GC,&LR,&LC) == 6)
  200. {
  201. posible = true;
  202. counter = 0;
  203. inR = R;
  204. inC = C;
  205. pomGR = GR;
  206. pomGC = GC;
  207. setBoolean(GR,GC,LR,LC,right,top,convert);
  208.  
  209. end = new Node[20];
  210. createEnd(end, LR, LC);
  211.  
  212. while( (pomVal = isIn(pomGR, pomGC, end, R, C, LR, LC)) == -1 ) {
  213. setBoolean(pomGR,pomGC,LR,LC,right,top,convert);
  214. if( top && right && convert )
  215. {
  216. pomGR = pomGR - 2;
  217. pomGC = pomGC + 1;
  218. }
  219. else if( top && right && !convert )
  220. {
  221. pomGR = pomGR - 1;
  222. pomGC = pomGC + 2;
  223. }
  224. //--------------
  225. else if( top && !right && convert )
  226. {
  227. pomGR = pomGR - 2;
  228. pomGC = pomGC - 1;
  229. }
  230. else if( top && !right && !convert )
  231. {
  232. pomGR = pomGR - 1;
  233. pomGC = pomGC - 2;
  234. }
  235. //--------------
  236. else if( !top && right && convert )
  237. {
  238. pomGR = pomGR + 2;
  239. pomGC = pomGC + 1;
  240. }
  241. else if( !top && right && !convert )
  242. {
  243. pomGR = pomGR + 1;
  244. pomGC = pomGC + 2;
  245. }
  246. //--------------
  247. else if( !top && !right && convert )
  248. {
  249. pomGR = pomGR + 2;
  250. pomGC = pomGC - 1;
  251. }
  252. else if( !top && !right && !convert )
  253. {
  254. pomGR = pomGR + 1;
  255. pomGC = pomGC - 2;
  256. }
  257. if( !canGo(pomGR,pomGC,R,C) )
  258. {
  259. posible = false;
  260. break;
  261. }
  262.  
  263. counter ++;
  264. }
  265. counter += pomVal;
  266.  
  267. if(posible)
  268. cout << counter << endl;
  269. else
  270. cout << "impossible" << endl;
  271. }
  272.  
  273.  
  274. return 0;
  275. }
  276.  

Diff to submission s1015

grasshop.cpp

--- c4.s1015.cteam001.grasshop.cpp.0.grasshop.cpp
+++ c4.s1172.cteam001.grasshop.cpp.0.grasshop.cpp
@@ -14,7 +14,5 @@
 {
         bool can = false;
-        if(GR >= 1 && GR <= R)
-                can = true;
-        if(GC >= 1 && GC <= C)
+        if(GR >= 1 && GR <= R && GC >= 1 && GC <= C)
                 can = true;
         else
@@ -23,4 +21,41 @@
         return can;
 }
+bool isPosib(Node * end, int i, int R, int C)
+{
+        if( !canGo(end[i].r ,end[i].c,R,C) )
+                return false;
+                
+        if( i == 0 || i == 2 || i == 3 || i == 7 || i == 12 || i == 16 || i == 17 || i == 19 )
+                return true;
+        else
+        {
+                if( i == 1 )
+                        return ( isPosib(end, 3, R, C) || isPosib(end, 7, R, C) );
+                else if( i == 4 )
+                        return ( isPosib(end, 12, R, C) || isPosib(end, 2, R, C) );
+                else if( i == 6 )
+                        return ( isPosib(end, 16, R, C) || isPosib(end, 0, R, C) );
+                else if( i == 8 )
+                        return ( isPosib(end, 17, R, C) || isPosib(end, 0, R, C) );
+                else if( i == 11 )
+                        return ( isPosib(end, 19, R, C) || isPosib(end, 2, R, C) );
+                else if( i == 13 )
+                        return ( isPosib(end, 19, R, C) || isPosib(end, 3, R, C) );
+                else if( i == 15 )
+                        return ( isPosib(end, 17, R, C) || isPosib(end, 7, R, C) );
+                else if( i == 18 )
+                        return ( isPosib(end, 12, R, C) || isPosib(end, 16, R, C) );
+                else if( i == 5 )
+                        return ( isPosib(end, 8, R, C) || isPosib(end, 11, R, C) );
+                else if( i == 9 )
+                        return ( isPosib(end, 1, R, C) || isPosib(end, 18, R, C) );
+                else if( i == 10 )
+                        return ( isPosib(end, 1, R, C) || isPosib(end, 18, R, C) );
+                else if( i == 14 )
+                        return ( isPosib(end, 8, R, C) || isPosib(end, 11, R, C) );
+                
+        }
+        return false;
+}
 
 int isIn(int r, int c, Node* end,int Rgride, int Cgride, int LR, int LC)
@@ -32,10 +67,11 @@
                 if( end[i].r == r && end[i].c == c )
                 {
-                        if( canGo(end[i].r ,end[i].c,Rgride,Cgride) && (
-                                canGo(end[i].r+2 ,end[i].c+2,Rgride,Cgride) || 
-                                canGo(end[i].r+2 ,end[i].c-2,Rgride,Cgride) || 
-                                canGo(end[i].r-2 ,end[i].c+2,Rgride,Cgride) || 
-                                canGo(end[i].r-2 ,end[i].c+2,Rgride,Cgride) ) )
-                                return end[i].value;
+                        if( canGo(end[i].r ,end[i].c,Rgride,Cgride) )
+                        {
+                                if( isPosib(end,i,Rgride,Cgride) )
+                                        return end[i].value;
+                                else
+                                        return -1;
+                        }
                         else
                                 return -1;