Source code for submission s879

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 = ~0;
  175. 	scanf("%u %u %u %u %u %u", &aa, &ab, &ba, &bb, &ca, &cb);
  176. 	if (aa == ~0)
  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.