Source code for submission s635

Grasshop.java

  1. import java.util.*;
  2. import java.math.*;
  3. import java.io.*;
  4. import java.text.*;
  5.  
  6.  
  7. public class Grasshop {
  8. static String line, newline;
  9.  
  10. static int xspan, yspan, pos, x0, y0, xt, yt, steps;
  11. static StringTokenizer st;
  12.  
  13. static ArrayList<int[]> nodes = new ArrayList<int[]>();
  14. static ArrayList<int[]> newnodes = new ArrayList<int[]>();
  15.  
  16. static boolean[][] visited = new boolean[101][101];
  17. static boolean foundEnd = false;
  18.  
  19. static void examineOutnodes(int x, int y){
  20. int xnew, ynew;
  21.  
  22. // A
  23. xnew = x-2;
  24. ynew = y+1;
  25. if(valid(xnew,ynew) && !visited[xnew][ynew]){
  26. newnodes.add(new int[]{xnew,ynew});
  27. visited[xnew][ynew]=true;
  28. if(xnew==xt && ynew==yt) {
  29. foundEnd=true;
  30. return;
  31. }
  32. }
  33. // A
  34. xnew = x+2;
  35. ynew = y+1;
  36. if(valid(xnew,ynew) && !visited[xnew][ynew]){
  37. newnodes.add(new int[]{xnew,ynew});
  38. visited[xnew][ynew]=true;
  39. if(xnew==xt && ynew==yt) {
  40. foundEnd=true;
  41. return;
  42. }
  43. }
  44. // B
  45. xnew = x-2;
  46. ynew = y-1;
  47. if(valid(xnew,ynew) && !visited[xnew][ynew]){
  48. newnodes.add(new int[]{xnew,ynew});
  49. visited[xnew][ynew]=true;
  50. if(xnew==xt && ynew==yt) {
  51. foundEnd=true;
  52. return;
  53. }
  54. }
  55. // B
  56. xnew = x+2;
  57. ynew = y-1;
  58. if(valid(xnew,ynew) && !visited[xnew][ynew]){
  59. newnodes.add(new int[]{xnew,ynew});
  60. visited[xnew][ynew]=true;
  61. if(xnew==xt && ynew==yt) {
  62. foundEnd=true;
  63. return;
  64. }
  65. }
  66. // C
  67. xnew = x-1;
  68. ynew = y+2;
  69. if(valid(xnew,ynew) && !visited[xnew][ynew]){
  70. newnodes.add(new int[]{xnew,ynew});
  71. visited[xnew][ynew]=true;
  72. if(xnew==xt && ynew==yt) {
  73. foundEnd=true;
  74. return;
  75. }
  76. }
  77. // C
  78. xnew = x-1;
  79. ynew = y-2;
  80. if(valid(xnew,ynew) && !visited[xnew][ynew]){
  81. newnodes.add(new int[]{xnew,ynew});
  82. visited[xnew][ynew]=true;
  83. if(xnew==xt && ynew==yt) {
  84. foundEnd=true;
  85. return;
  86. }
  87. }
  88. // D
  89. xnew = x+1;
  90. ynew = y+2;
  91. if(valid(xnew,ynew) && !visited[xnew][ynew]){
  92. newnodes.add(new int[]{xnew,ynew});
  93. visited[xnew][ynew]=true;
  94. if(xnew==xt && ynew==yt) {
  95. foundEnd=true;
  96. return;
  97. }
  98. }
  99. // D
  100. xnew = x+1;
  101. ynew = y-2;
  102. if(valid(xnew,ynew) && !visited[xnew][ynew]){
  103. newnodes.add(new int[]{xnew,ynew});
  104. visited[xnew][ynew]=true;
  105. if(xnew==xt && ynew==yt) {
  106. foundEnd=true;
  107. return;
  108. }
  109. }
  110. }
  111.  
  112. static void findWay(){
  113. nodes.clear();
  114. newnodes.clear();
  115. // end == start
  116. if(xt==x0 && yt==y0){
  117. steps=0;
  118. return;
  119. }
  120.  
  121. if(!valid(xt,yt) || !valid(x0,y0)){
  122. steps=-1;
  123. return;
  124. }
  125.  
  126.  
  127. visited[x0][y0] = true;
  128. nodes.add(new int[]{x0,y0});
  129.  
  130. while(foundEnd==false && !nodes.isEmpty()){
  131. steps++;
  132. for(int[] node : nodes){
  133. examineOutnodes(node[0],node[1]);
  134. }
  135. nodes.clear();
  136. nodes.addAll(newnodes);
  137. newnodes.clear();
  138. }
  139.  
  140. if(!foundEnd) steps=-1;
  141. return;
  142.  
  143. }
  144.  
  145. static boolean valid(int x, int y){
  146. return (x>=1 && x<=xspan && y>=1 && y<=yspan);
  147. }
  148. /**
  149.   * @param args the command line arguments
  150.   */
  151. public static void main(String[] args) throws Exception{
  152. while( (line=br.readLine()) != null) {
  153. st = new StringTokenizer(line);
  154. xspan = Integer.valueOf(st.nextToken());
  155. yspan = Integer.valueOf(st.nextToken());
  156. x0 = Integer.valueOf(st.nextToken());
  157. y0 = Integer.valueOf(st.nextToken());
  158. xt = Integer.valueOf(st.nextToken());
  159. yt = Integer.valueOf(st.nextToken());
  160.  
  161. // nulovani
  162. for(int xi=1;xi<=xspan;xi++){
  163. for(int yi=1;yi<yspan;yi++){
  164. visited[xi][yi] = false;
  165. }
  166. }
  167. foundEnd = false;
  168. steps = 0;
  169.  
  170. findWay();
  171. if(steps==-1)
  172. System.out.println("impossible");
  173. else
  174. System.out.println(steps);
  175.  
  176.  
  177.  
  178. }
  179.  
  180.  
  181. }
  182.  
  183. }
  184.