Source code for submission s892

Go to diff to previous submission

greg.c

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

Diff to submission s879

greg.c

--- c4.s879.cteam073.grasshop.c.0.greg.c
+++ c4.s892.cteam073.grasshop.c.0.greg.c
@@ -3,5 +3,5 @@
 #include <unistd.h>
 
-
+#include <string.h>
 
 static int found;
@@ -18,12 +18,5 @@
 void clean(struct memo *m)
 {
-        int x;
-        int y;
-        for (x = 0; x < m->x; x++){
-        for (y = 0; y < m->y; y++){
-                m->s[x][y] = 'a';
-        }
-        }
-
+        memset(m->s, 'a', m->x * m->y * sizeof(char));
 }