Grasshop.java
import java.util.*;
import java.io.*;
class Grasshop {
while ( line != null ) {
String[] p
= line.
split( " " ); 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 ) ); line = br.readLine();
}
}
private static final class State implements Comparable<State> {
int r; int c; int len;
public State( int r, int c, int len ) { this.r = r; this.c = c; this.len = len; }
public int compareTo( State s ) {
if ( this.len == s.len ) return 0;
return this.len < s.len ? -1 : 1;
}
}
private static final int[] dirr = { -2, -2, -1, -1, 1, 1, 2, 2 };
private static final int[] dirc = { -1, 1, -2, 2, -2, 2, -1, 1 };
private static final String solve
( final int R,
final int C,
final int gr,
final int gc,
final int lr,
final int lc
) { boolean[][] board = new boolean[R][C];
for ( int ri
= 0; ri
< R
; ++ri
) Arrays.
fill( board
[ri
],
false ); PriorityQueue<State> pq = new PriorityQueue<State>();
pq.add( new State(gr, gc, 0) );
while ( !pq.isEmpty() ) {
State act = pq.poll();
if ( act.
r == lr
&& act.
c == lc
) return Integer.
toString(act.
len);
for ( int i = 0; i < dirr.length; ++i ) {
int nr = act.r + dirr[i];
if ( nr < 0 || nr >= R ) continue;
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 ) );
}
}
return "impossible";
}
private static final int toi
( String s
) { return Integer.
parseInt(s
); } }