Source code for submission s663

Go to diff to previous submission

Grasshop.java

  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Grasshop {
  5.  
  6. public static void main( String[] args ) throws Exception {
  7. String line = br.readLine();
  8. while ( line != null ) {
  9. String[] p = line.split( " " );
  10. System.out.println( solve( toi(p[0]), toi(p[1]), toi(p[2]) - 1, toi(p[3]) - 1, toi(p[4]) - 1, toi(p[5]) - 1 ) );
  11. line = br.readLine();
  12. }
  13. }
  14.  
  15. private static final class State implements Comparable<State> {
  16. int r; int c; int len;
  17.  
  18. public State( int r, int c, int len ) { this.r = r; this.c = c; this.len = len; }
  19.  
  20. public int compareTo( State s ) {
  21. if ( this.len == s.len ) return 0;
  22. return this.len < s.len ? -1 : 1;
  23. }
  24. }
  25.  
  26. private static final int[] dirr = { -2, -2, -1, -1, 1, 1, 2, 2 };
  27. private static final int[] dirc = { -1, 1, -2, 2, -2, 2, -1, 1 };
  28.  
  29. private static final String solve( final int R, final int C, final int gr, final int gc, final int lr, final int lc ) {
  30. boolean[][] board = new boolean[R][C];
  31. for ( int ri = 0; ri < R; ++ri ) Arrays.fill( board[ri], false );
  32. PriorityQueue<State> pq = new PriorityQueue<State>();
  33. pq.add( new State(gr, gc, 0) );
  34. while ( !pq.isEmpty() ) {
  35. State act = pq.poll();
  36. if ( act.r == lr && act.c == lc ) return Integer.toString(act.len);
  37.  
  38. for ( int i = 0; i < dirr.length; ++i ) {
  39. int nr = act.r + dirr[i];
  40. if ( nr < 0 || nr >= R ) continue;
  41. int nc = act.c + dirc[i];
  42. if ( nc < 0 || nc >= C ) continue;
  43. if ( !board[nr][nc] ) {
  44. board[nr][nc] = true;
  45. pq.add( new State( nr, nc, act.len + 1 ) );
  46. }
  47. }
  48. }
  49. return "impossible";
  50. }
  51. private static final int toi( String s ) { return Integer.parseInt(s); }
  52. }
  53.  

Diff to submission s660

Grasshop.java

--- c4.s660.cteam046.grasshop.java.0.Grasshop.java
+++ c4.s663.cteam046.grasshop.java.0.Grasshop.java
@@ -42,6 +42,8 @@
                                 int nc = act.c + dirc[i];
                                 if ( nc < 0 || nc >= C ) continue;
-                                board[nr][nc] = true;
-                                pq.add( new State( nr, nc, act.len + 1 ) );
+                                if ( !board[nr][nc] ) {
+                                        board[nr][nc] = true;
+                                        pq.add( new State( nr, nc, act.len + 1 ) );
+                                }
                         }
                 }