Source code for submission s1043

Go to diff to previous submission

grasshop.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <deque>
  5. #include <string>
  6. using namespace std;
  7.  
  8. typedef struct 
  9. {
  10. 	int x;
  11. 	int y;
  12. } bod;
  13. int pole[100][100];
  14. bool jevectverci(int x, int y, int r, int c)
  15. {
  16. 	return ((x >= 0 && x < r) && (y >= 0 && y< c))?true:false; 
  17. }
  18.  
  19. int main()
  20. {
  21. 	int r, c, gr, gc, lr, lc;
  22. 	while(scanf("%d %d %d %d %d %d", &r, &c, &gr, &gc, &lr, &lc) == 6)
  23. 	{
  24. 		for(int i=0; i<r; i++)
  25. 			for(int j=0; j<c; j++)
  26. 			{
  27. 				pole[i][j] = 0;
  28. 			}
  29. 		pole[lr-1][lc-1] = -1;
  30.  
  31. 		deque<bod> prosle;
  32. 		bod b;
  33. 		b.x = gr-1;
  34. 		b.y = gc-1;
  35. 		prosle.push_front(b);
  36.  
  37. 		deque<bod> nove;
  38.  
  39. 		int vysledek = 0;
  40. 		int pocet = 1;
  41. 		int max = 0;
  42. 		pole[(prosle.back()).x][(prosle.back()).y] = pocet;
  43. 		bool nenalezeno = true;
  44. 		while(nenalezeno && max < 10000)
  45. 		{	
  46. 			max++;
  47. 			if (!nove.empty())
  48. 				prosle = nove;
  49. 			nove.clear();
  50. 			pocet++;
  51. 			while(prosle.size() > 0)
  52. 			{
  53. 				if (jevectverci((prosle.back()).x+2,(prosle.back()).y+1,r,c))
  54. 				{
  55. 					if (pole[(prosle.back()).x+2][(prosle.back()).y+1] == 0)
  56. 					{
  57. 						pole[(prosle.back()).x+2][(prosle.back()).y+1] = pocet;
  58. 						b.x = (prosle.back()).x+2;
  59. 						b.y = (prosle.back()).y+1;
  60. 						nove.push_front(b);
  61. 					}
  62. 					else if (pole[(prosle.back()).x+2][(prosle.back()).y+1] == -1)
  63. 					{
  64. 						vysledek = pocet;
  65. 						nenalezeno = false;
  66. 						break;
  67. 					}
  68. 				}
  69. 				if (jevectverci((prosle.back()).x+2,(prosle.back()).y-1,r,c))
  70. 				{
  71. 					if (pole[(prosle.back()).x+2][(prosle.back()).y-1] == 0)
  72. 					{
  73. 						pole[(prosle.back()).x+2][(prosle.back()).y-1] = pocet;
  74. 						b.x = (prosle.back()).x+2;
  75. 						b.y = (prosle.back()).y-1;
  76. 						nove.push_front(b);
  77. 					}
  78. 					else if (pole[(prosle.back()).x+2][(prosle.back()).y-1] == -1)
  79. 					{
  80. 						vysledek = pocet;
  81. 						nenalezeno = false;
  82. 						break;
  83. 					}
  84. 				}
  85. 				if (jevectverci((prosle.back()).x-2,(prosle.back()).y+1,r,c))
  86. 				{
  87. 					if (pole[(prosle.back()).x-2][(prosle.back()).y+1] == 0)
  88. 					{
  89. 						pole[(prosle.back()).x-2][(prosle.back()).y+1] = pocet;
  90. 						b.x = (prosle.back()).x-2;
  91. 						b.y = (prosle.back()).y+1;
  92. 						nove.push_front(b);
  93. 					}
  94. 					else if (pole[(prosle.back()).x-2][(prosle.back()).y+1] == -1)
  95. 					{
  96. 						vysledek = pocet;
  97. 						nenalezeno = false;
  98. 						break;
  99. 					}
  100. 				}
  101. 				if (jevectverci((prosle.back()).x-2,(prosle.back()).y-1,r,c))
  102. 				{
  103. 					if (pole[(prosle.back()).x-2][(prosle.back()).y-1] == 0)
  104. 					{
  105. 						pole[(prosle.back()).x-2][(prosle.back()).y-1] = pocet;
  106. 						b.x = (prosle.back()).x-2;
  107. 						b.y = (prosle.back()).y-1;
  108. 						nove.push_front(b);
  109. 					}
  110. 					else if (pole[(prosle.back()).x-2][(prosle.back()).y-1] == -1)
  111. 					{
  112. 						vysledek = pocet;
  113. 						nenalezeno = false;
  114. 						break;
  115. 					}
  116. 				}
  117. 				if (jevectverci((prosle.back()).x+1,(prosle.back()).y+2,r,c))
  118. 				{
  119. 					if (pole[(prosle.back()).x+1][(prosle.back()).y+2] == 0)
  120. 					{
  121. 						pole[(prosle.back()).x+1][(prosle.back()).y+2] = pocet;
  122. 						b.x = (prosle.back()).x+1;
  123. 						b.y = (prosle.back()).y+2;
  124. 						nove.push_front(b);
  125. 					}
  126. 					else if (pole[(prosle.back()).x+1][(prosle.back()).y+2] == -1)
  127. 					{
  128. 						vysledek = pocet;
  129. 						nenalezeno = false;
  130. 						break;
  131. 					}
  132. 				}
  133. 				if (jevectverci((prosle.back()).x+1,(prosle.back()).y-2,r,c))
  134. 				{
  135. 					if (pole[(prosle.back()).x+1][(prosle.back()).y-2] == 0)
  136. 					{
  137. 						pole[(prosle.back()).x+1][(prosle.back()).y-2] = pocet;
  138. 						b.x = (prosle.back()).x+1;
  139. 						b.y = (prosle.back()).y-2;
  140. 						nove.push_front(b);
  141. 					}
  142. 					else if (pole[(prosle.back()).x+1][(prosle.back()).y-2] == -1)
  143. 					{
  144. 						vysledek = pocet;
  145. 						nenalezeno = false;
  146. 						break;
  147.  
  148. 					}
  149. 				}
  150. 				if (jevectverci((prosle.back()).x-1,(prosle.back()).y+2,r,c))
  151. 				{
  152. 					if (pole[(prosle.back()).x-1][(prosle.back()).y+2] == 0)
  153. 					{
  154. 						pole[(prosle.back()).x-1][(prosle.back()).y+2] = pocet;
  155. 						b.x = (prosle.back()).x-1;
  156. 						b.y = (prosle.back()).y+2;
  157. 						nove.push_front(b);
  158. 					}
  159. 					else if (pole[(prosle.back()).x-1][(prosle.back()).y+2] == -1)
  160. 					{
  161. 						vysledek = pocet;
  162. 						nenalezeno = false;
  163. 						break;
  164. 					}
  165. 				}
  166. 				if (jevectverci((prosle.back()).x-1,(prosle.back()).y-2,r,c))
  167. 				{
  168. 					if (pole[(prosle.back()).x-1][(prosle.back()).y-2] == 0)
  169. 					{
  170. 						pole[(prosle.back()).x-1][(prosle.back()).y-2] = pocet;
  171. 						b.x = (prosle.back()).x-1;
  172. 						b.y = (prosle.back()).y-2;
  173. 						nove.push_front(b);
  174. 					}
  175. 					else if (pole[(prosle.back()).x-1][(prosle.back()).y-2] == -1)
  176. 					{
  177. 						vysledek = pocet;
  178. 						nenalezeno = false;
  179. 						break;
  180. 					}
  181. 				}
  182. 				prosle.pop_back();
  183. 			}
  184. 		}
  185. /*
  186. 		for(int i=0; i<r; i++)
  187. 		{
  188. 			for(int j=0; j<c; j++)
  189. 			{
  190. 				printf("%d ",pole[i][j]);
  191. 			}
  192. 			printf("\n");
  193. 		}
  194. 		int max = -1;
  195. 		for(int i=0; i<r; i++)
  196. 			for(int j=0; j<c; j++)
  197. 			{
  198. 				if(pole[i][j] > max)
  199. 					max = pole[i][j];
  200. 			}*/
  201. 		if (vysledek == 0)
  202. 			printf("impossible\n");
  203. 		else
  204. 			printf("%d\n",vysledek-1);
  205. 	}
  206. 	return 0;
  207. }
  208.  
  209.  

Diff to submission s1037

grasshop.cpp

--- c4.s1037.cteam106.grasshop.cpp.0.grasshop.cpp
+++ c4.s1043.cteam106.grasshop.cpp.0.grasshop.cpp
@@ -42,5 +42,5 @@
                 pole[(prosle.back()).x][(prosle.back()).y] = pocet;
                 bool nenalezeno = true;
-                while(nenalezeno && max < 100)
+                while(nenalezeno && max < 10000)
                 {       
                         max++;