Source code for submission s900

Go to diff to previous submission

greg.c

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <unistd.h>
  4.  
  5.  
  6.  
  7. static int found;
  8.  
  9. struct memo {
  10. char s[1000][1000];
  11. int x;
  12. int y;
  13. int gx;
  14. int gy;
  15. };
  16.  
  17.  
  18. void clean(struct memo *m)
  19. {
  20. int x;
  21. int y;
  22. for (x = 0; x < m->x; x++){
  23. for (y = 0; y < m->y; y++){
  24. m->s[x][y] = 'a';
  25. }
  26. }
  27.  
  28. }
  29.  
  30. int isvisit(struct memo *m, int x, int y)
  31. {
  32. return (m->s[x][y] == 'q');
  33. }
  34.  
  35. void markr(struct memo *m, int x, int y)
  36. {
  37.  
  38. #ifdef DEBUG
  39. printf("%s %i %i \n",__func__, x, y);
  40. #endif
  41.  
  42. if (x >= m->x)
  43. return;
  44.  
  45. if (y >= m->y)
  46. return;
  47.  
  48. if (x < 0)
  49. return;
  50.  
  51. if (y < 0)
  52. return;
  53.  
  54. if (isvisit(m, x, y))
  55. return;
  56.  
  57.  
  58. m->s[x][y] = 'r';
  59. /*
  60. sleep (1);
  61. */
  62. /*
  63. sleep (1);
  64. */
  65. }
  66.  
  67.  
  68. void hop(struct memo *m, int x, int y)
  69. {
  70. #ifdef DEBUG
  71. printf("%s %i %i \n",__func__, x, y);
  72. #endif
  73.  
  74.  
  75. if (x >= m->x)
  76. return;
  77.  
  78. if (y >= m->y)
  79. return;
  80.  
  81. if (x < 0)
  82. return;
  83.  
  84. if (y < 0)
  85. return;
  86.  
  87. if (isvisit(m, x, y))
  88. return;
  89.  
  90. if (m->s[x][y] != 'r')
  91. return;
  92.  
  93. m->s[x][y] = 'q';
  94.  
  95. if ((x == m->gx) && (y == m->gy)) {
  96. found = 1;
  97. return;
  98. }
  99.  
  100. markr(m, x+1, y+2);
  101. markr(m, x+1, y-2);
  102. markr(m, x-1, y+2);
  103. markr(m, x-1, y-2);
  104. markr(m, x+2, y+1);
  105. markr(m, x+2, y-1);
  106. markr(m, x-2, y+1);
  107. markr(m, x-2, y-1);
  108.  
  109. /*
  110. sleep (1);
  111. /*
  112. sleep (1);
  113. */
  114.  
  115. }
  116.  
  117. int dohop(struct memo *m)
  118. {
  119. #ifdef DEBUG
  120. printf("%s \n",__func__);
  121. #endif
  122.  
  123. int nnx[1000];
  124. int nny[1000];
  125. int off =0;
  126.  
  127.  
  128. /* start child in r-s*/
  129.  
  130. int ch = 0;
  131. int nx, ny;
  132.  
  133. for (nx = 0; nx < m->x; nx++) {
  134. for (ny = 0; ny < m->y; ny++) {
  135. if (m->s[nx][ny] == 'r') {
  136. nnx[off] = nx;
  137. nny[off] = ny;
  138. off++;
  139. }
  140. if (found != 0) {
  141. /* found++;
  142. */
  143. return 0;
  144. }
  145. }
  146. }
  147.  
  148. int i;
  149. for (i = 0; i < off ; i++){
  150.  
  151. hop(m, nnx[i], nny[i]);
  152.  
  153. }
  154.  
  155.  
  156. return off;
  157. }
  158.  
  159.  
  160.  
  161. int main(void)
  162.  
  163. {
  164.  
  165.  
  166. #ifdef DEBUG
  167. printf("%s \n",__func__);
  168. #endif
  169.  
  170. unsigned int aa, ab, ba, bb, ca, cb;
  171. while (1){
  172. found = 0;
  173.  
  174. aa = 654645645;
  175. scanf("%u %u %u %u %u %u", &aa, &ab, &ba, &bb, &ca, &cb);
  176. if (aa == 654645645)
  177. exit(0);
  178.  
  179. struct memo m;
  180. clean(&m);
  181. m.x = aa;
  182. m.y = ab;
  183. m.gx = ca-1;
  184. m.gy = cb-1;
  185.  
  186. m.s[ba-1][bb-1] = 'r';
  187.  
  188. int count = 0;
  189.  
  190. while (dohop(&m) && (found == 0)) {count++;
  191.  
  192.  
  193. #ifdef DEBUG
  194. printf("---------- \n",__func__);
  195. #endif
  196.  
  197. }
  198.  
  199. if (found) {
  200.  
  201. printf("%i\n", count);
  202.  
  203. } else {
  204. printf("impossible\n");
  205. }
  206.  
  207. }}
  208.  

Diff to submission s892

greg.c

--- c4.s892.cteam073.grasshop.c.0.greg.c
+++ c4.s900.cteam073.grasshop.c.0.greg.c
@@ -3,5 +3,5 @@
 #include <unistd.h>
 
-#include <string.h>
+
 
 static int found;
@@ -18,5 +18,12 @@
 void clean(struct memo *m)
 {
-        memset(m->s, 'a', m->x * m->y * sizeof(char));
+        int x;
+        int y;
+        for (x = 0; x < m->x; x++){
+        for (y = 0; y < m->y; y++){
+                m->s[x][y] = 'a';
+        }
+        }
+
 }
 
@@ -165,7 +172,7 @@
         found = 0;
 
-        aa = ~0;
+        aa = 654645645;
         scanf("%u %u %u %u %u %u", &aa, &ab, &ba, &bb, &ca, &cb);
-        if (aa == ~0)
+        if (aa == 654645645)
                 exit(0);