Source code for submission s670

Grasshop.java

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5.  
  6.  
  7. public class Grasshop {
  8.  
  9. /**
  10. * @param args
  11. */
  12. public static void main(String[] args) throws Exception {
  13.  
  14. String s;
  15. int m, n, gm, gn, gv, tm, tn;
  16. LinkedList<Integer> mq = new LinkedList<Integer>();
  17. LinkedList<Integer> nq = new LinkedList<Integer>();
  18. LinkedList<Integer> vq = new LinkedList<Integer>();
  19.  
  20. while (true)
  21. {
  22. s = br.readLine();
  23. if (s == null || s.length()==0) break;
  24. String[] ss = s.split(" ");
  25. m = Integer.parseInt(ss[0]);
  26. n = Integer.parseInt(ss[1]);
  27. gm = Integer.parseInt(ss[2]) - 1;
  28. gn = Integer.parseInt(ss[3]) - 1;
  29. tm = Integer.parseInt(ss[4]) - 1;
  30. tn = Integer.parseInt(ss[5]) - 1;
  31.  
  32. int[][] pole = new int[m][n];
  33. for (int i = 0; i < n; i++)
  34. for (int j = 0; j < m; j++)
  35. pole[j][i] = Integer.MAX_VALUE;
  36.  
  37. vq.clear();
  38. mq.clear();
  39. nq.clear();
  40.  
  41. vq.addLast(0);
  42. mq.addLast(gm);
  43. nq.addLast(gn);
  44.  
  45. boolean done = false;
  46.  
  47. while (!vq.isEmpty())
  48. {
  49. gv = vq.removeFirst();
  50. gm = mq.removeFirst();
  51. gn = nq.removeFirst();
  52.  
  53. if (gm == tm && gn == tn)
  54. {
  55. System.out.println(gv);
  56. done = true;
  57. break;
  58. }
  59.  
  60. if (gm >= 0 && gn >= 0 &&
  61. gm < m && gn < n &&
  62. pole[gm][gn] > gv)
  63. {
  64. pole[gm][gn] = gv;
  65.  
  66. vq.addLast(gv + 1);
  67. mq.addLast(gm + 2);
  68. nq.addLast(gn + 1);
  69.  
  70. vq.addLast(gv + 1);
  71. mq.addLast(gm + 1);
  72. nq.addLast(gn + 2);
  73.  
  74. vq.addLast(gv + 1);
  75. mq.addLast(gm - 2);
  76. nq.addLast(gn - 1);
  77.  
  78. vq.addLast(gv + 1);
  79. mq.addLast(gm - 1);
  80. nq.addLast(gn - 2);
  81.  
  82. vq.addLast(gv + 1);
  83. mq.addLast(gm - 2);
  84. nq.addLast(gn + 1);
  85.  
  86. vq.addLast(gv + 1);
  87. mq.addLast(gm - 1);
  88. nq.addLast(gn + 2);
  89.  
  90. vq.addLast(gv + 1);
  91. mq.addLast(gm + 2);
  92. nq.addLast(gn - 1);
  93.  
  94. vq.addLast(gv + 1);
  95. mq.addLast(gm + 1);
  96. nq.addLast(gn - 2);
  97. }
  98. }
  99.  
  100. if (!done) System.out.println("impossible");
  101. }
  102. }
  103.  
  104. }
  105.