Source code for submission s1266

Grasshop.java

  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3. import java.util.Scanner;
  4.  
  5. import javax.sql.PooledConnection;
  6. import javax.swing.JEditorPane;
  7.  
  8. public class Grasshop {
  9. static void vypis(int[][] pole) {
  10. for (int i = 0; i < pole.length; i++) {
  11. for (int j = 0; j < pole.length; j++) {
  12. System.out.print(pole[i][j] + " ");
  13. }
  14. System.out.println();
  15. }
  16. System.out.println();
  17. }
  18.  
  19. static void skakaj(Queue<Integer> rad, int aktualnyx, int aktualnyy,
  20. int aktualnyh, int[][] poleVysledkov) {
  21. if (poleVysledkov[aktualnyx + 2][aktualnyy + 1] > aktualnyh + 1
  22. || poleVysledkov[aktualnyx + 2][aktualnyy + 1] == -1) {
  23. rad.add(aktualnyx + 2);
  24. rad.add(aktualnyy + 1);
  25. rad.add(aktualnyh + 1);
  26. }
  27. if (poleVysledkov[aktualnyx + 1][aktualnyy + 2] > aktualnyh + 1
  28. || poleVysledkov[aktualnyx + 1][aktualnyy + 2] == -1) {
  29. rad.add(aktualnyx + 1);
  30. rad.add(aktualnyy + 2);
  31. rad.add(aktualnyh + 1);
  32. }
  33. if (poleVysledkov[aktualnyx - 2][aktualnyy - 1] > aktualnyh + 1
  34. || poleVysledkov[aktualnyx - 2][aktualnyy - 1] == -1) {
  35. rad.add(aktualnyx - 2);
  36. rad.add(aktualnyy - 1);
  37. rad.add(aktualnyh + 1);
  38. }
  39. if (poleVysledkov[aktualnyx - 1][aktualnyy - 2] > aktualnyh + 1
  40. || poleVysledkov[aktualnyx - 1][aktualnyy - 2] == -1) {
  41. rad.add(aktualnyx - 1);
  42. rad.add(aktualnyy - 2);
  43. rad.add(aktualnyh + 1);
  44. }
  45.  
  46. // -----------------------
  47. if (poleVysledkov[aktualnyx - 2][aktualnyy + 1] > aktualnyh + 1
  48. || poleVysledkov[aktualnyx - 2][aktualnyy + 1] == -1) {
  49. rad.add(aktualnyx - 2);
  50. rad.add(aktualnyy + 1);
  51. rad.add(aktualnyh + 1);
  52. }
  53. if (poleVysledkov[aktualnyx - 1][aktualnyy + 2] > aktualnyh + 1
  54. || poleVysledkov[aktualnyx - 1][aktualnyy + 2] == -1) {
  55. rad.add(aktualnyx - 1);
  56. rad.add(aktualnyy + 2);
  57. rad.add(aktualnyh + 1);
  58. }
  59. if (poleVysledkov[aktualnyx + 2][aktualnyy - 1] > aktualnyh + 1
  60. || poleVysledkov[aktualnyx + 2][aktualnyy - 1] == -1) {
  61. rad.add(aktualnyx + 2);
  62. rad.add(aktualnyy - 1);
  63. rad.add(aktualnyh + 1);
  64. }
  65. if (poleVysledkov[aktualnyx + 1][aktualnyy - 2] > aktualnyh + 1
  66. || poleVysledkov[aktualnyx + 1][aktualnyy - 2] == -1) {
  67. rad.add(aktualnyx + 1);
  68. rad.add(aktualnyy - 2);
  69. rad.add(aktualnyh + 1);
  70. }
  71. }
  72.  
  73. /**
  74. * @param args
  75. */
  76. public static void main(String[] args) {
  77. final int posun = 2;
  78. Scanner s = new Scanner(System.in);
  79. int riadkov, stlpcov, sx, sy, kx, ky;
  80. int[][] poleVysledkov;
  81. boolean naslaSaCesta = false;
  82. int aktualnyx, aktualnyy, aktualnyh;
  83. while (s.hasNextLine()) {
  84. riadkov = s.nextInt();
  85. stlpcov = s.nextInt();
  86. sx = s.nextInt() + posun - 1;
  87. sy = s.nextInt() + posun - 1;
  88. kx = s.nextInt() + posun - 1;
  89. ky = s.nextInt() + posun - 1;
  90. poleVysledkov = new int[riadkov + 2 * posun][stlpcov + 2 * posun];
  91.  
  92. // daj minus jednotky
  93. for (int i = 0; i < poleVysledkov.length; i++) {
  94. for (int j = 0; j < poleVysledkov.length; j++) {
  95. poleVysledkov[i][j] = -2;
  96. }
  97. }
  98.  
  99. for (int i = posun; i < poleVysledkov.length - posun; i++) {
  100. for (int j = posun; j < poleVysledkov.length - posun; j++) {
  101. poleVysledkov[i][j] = -1;
  102. }
  103. }
  104. if(poleVysledkov.length<9)
  105. {
  106. //prehladaj do sirky
  107. poleVysledkov[sx][sy] = 0;
  108. Queue<Integer> rad=new LinkedList<Integer>();
  109. rad.add(sx);
  110. rad.add(sy);
  111. rad.add(0);
  112. naslaSaCesta=false;
  113. while(!rad.isEmpty())
  114. {
  115. aktualnyx=rad.poll();
  116. aktualnyy=rad.poll();
  117. aktualnyh=rad.poll();
  118.  
  119. if (aktualnyx==kx&&aktualnyy==ky)
  120. {
  121. naslaSaCesta=true;
  122. System.out.println(aktualnyh);
  123. break;
  124. }
  125. if (poleVysledkov[aktualnyx][aktualnyy]>aktualnyh||poleVysledkov[aktualnyx][aktualnyy]==-1)
  126. {
  127. poleVysledkov[aktualnyx][aktualnyy]=aktualnyh;
  128.  
  129. }
  130. skakaj(rad, aktualnyx, aktualnyy, aktualnyh, poleVysledkov);
  131.  
  132.  
  133. }
  134. if (!naslaSaCesta) System.out.println("impossible");
  135.  
  136.  
  137.  
  138.  
  139. }else {
  140. // este vymenit + zaciatocny nula
  141. int pom;
  142. if (sx > kx && sy > ky) {
  143. // vymeni
  144. pom = sx;
  145. sx = kx;
  146. kx = pom;
  147.  
  148. pom = sy;
  149. sy = ky;
  150. ky = pom;
  151.  
  152. }
  153. poleVysledkov[sx][sy] = 0;
  154.  
  155.  
  156. int[][] posuvnepole = new int[5][5];
  157. int[] pole = { 4, 1, 2, 1, 4 };
  158. posuvnepole[0] = pole;
  159. int[] pole1 = { 1, 2, 3, 2, 1 };
  160. posuvnepole[1] = pole1;
  161. int[] pole2 = { 2, 3, 0, 3, 2 };
  162. posuvnepole[2] = pole2;
  163. posuvnepole[3] = pole1;
  164. posuvnepole[4] = pole;
  165. for (int i = posun; i < poleVysledkov.length - posun; i++) {
  166. for (int j = posun; j < poleVysledkov.length - posun; j++) {
  167. if (poleVysledkov[i][j] != -2)
  168. // pre policko pricitaj mriezku
  169. for (int j2 = -2; j2 <= 2; j2++) {
  170. for (int k = -2; k <= 2; k++) {
  171. if (poleVysledkov[i + j2][j + k] > poleVysledkov[i][j]
  172. + posuvnepole[j2+2][k+2]
  173. || poleVysledkov[i + j2][j + k] == -1) {
  174. poleVysledkov[i + j2][j + k] = poleVysledkov[i][j]
  175. + posuvnepole[j2+2][k+2];
  176. }
  177.  
  178. }
  179. }
  180.  
  181. }
  182. }
  183. //vypis(poleVysledkov);
  184. System.out.println(poleVysledkov[kx][ky]);}
  185. }
  186. }
  187. }