Source code for submission s679

grasshop.java

  1.  
  2. import java.util.StringTokenizer;
  3. import java.io.BufferedReader;
  4. import java.io.InputStreamReader;
  5.  
  6. /**
  7.  *
  8.  * @author cteam049
  9.  */
  10. public class grasshop
  11. {
  12.  
  13. protected int r;
  14. protected int c;
  15. protected int gr;
  16. protected int gc;
  17. protected int lr;
  18. protected int lc;
  19.  
  20. protected int[][] field;
  21.  
  22.  
  23.  
  24. /**
  25.   * @param args the command line arguments
  26.   */
  27. public static void main( String[] args )
  28. {
  29. grasshop program = new grasshop();
  30. program.run();
  31. }
  32.  
  33.  
  34.  
  35. protected void run()
  36. {
  37. try
  38. {
  39. for ( ;; )
  40. {
  41. this.r = this.nextInt();
  42. this.c = this.nextInt();
  43. this.gr = this.nextInt();
  44. this.gc = this.nextInt();
  45. this.lr = this.nextInt();
  46. this.lc = this.nextInt();
  47.  
  48. this.field = new int[ this.r ][ this.c ];
  49. this.field[ this.gr - 1 ][ this.gc - 1 ] = 1;
  50.  
  51. if ( this.gr == this.lr && this.gc == this.lc )
  52. {
  53. System.out.println( "0" );
  54. continue;
  55. }
  56.  
  57. try
  58. {
  59. int num = 1;
  60. while ( this.makeJumps( num++ ) );
  61. System.out.println( "impossible" );
  62. }
  63. catch ( SuccessException e )
  64. {
  65. System.out.println( e.value );
  66. }
  67. }
  68. }
  69. catch ( Exception e )
  70. {
  71. e.printStackTrace();
  72. }
  73. }
  74.  
  75.  
  76. protected boolean makeJumps( int num ) throws SuccessException
  77. {
  78. boolean res = false;
  79.  
  80. for ( int i = 0; i < this.r; i++ )
  81. {
  82. for ( int j = 0; j < this.c; j++ )
  83. {
  84. if ( this.field[ i ][ j ] == num )
  85. {
  86. res = res | this.makeOneJump( i - 2, j - 1, num + 1 );
  87. res = res | this.makeOneJump( i - 2, j + 1, num + 1 );
  88. res = res | this.makeOneJump( i - 1, j + 2, num + 1 );
  89. res = res | this.makeOneJump( i + 1, j + 2, num + 1 );
  90. res = res | this.makeOneJump( i + 2, j + 1, num + 1 );
  91. res = res | this.makeOneJump( i + 2, j - 1, num + 1 );
  92. res = res | this.makeOneJump( i + 1, j - 2, num + 1 );
  93. res = res | this.makeOneJump( i - 1, j - 2, num + 1 );
  94. }
  95. }
  96. }
  97.  
  98. return res;
  99. }
  100.  
  101.  
  102.  
  103. protected boolean makeOneJump( int r, int c, int num) throws SuccessException
  104. {
  105. if ( r < 0 || c < 0 || r >= this.r || c >= this.c || this.field[ r ][ c ] != 0 )
  106. {
  107. return false;
  108. }
  109.  
  110. if ( r == this.lr - 1 && c == this.lc - 1 )
  111. {
  112. throw new SuccessException( num - 1 );
  113. }
  114.  
  115. this.field[ r ][ c ] = num;
  116. return true;
  117. }
  118.  
  119.  
  120.  
  121. protected class SuccessException extends Exception
  122. {
  123.  
  124. public int value;
  125.  
  126. public SuccessException( int value )
  127. {
  128. this.value = value;
  129. }
  130.  
  131. }
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138. /* INPUT READING */
  139.  
  140.  
  141.  
  142.  
  143. public String nextToken() throws Exception
  144. {
  145. while ( ! st.hasMoreTokens() )
  146. {
  147. st = new StringTokenizer( input.readLine() );
  148. }
  149. return st.nextToken();
  150. }
  151.  
  152.  
  153.  
  154. public int nextInt() throws Exception
  155. {
  156. return Integer.parseInt( this.nextToken() );
  157. }
  158.  
  159.  
  160.  
  161. public String nextLine() throws Exception
  162. {
  163. return input.readLine();
  164. }
  165.  
  166. }
  167.