Grasshop.java

import java.util.*;
import java.io.*;
 
class Grasshop {
 
	public static void main( String[] args ) throws Exception {
		final BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		String line = br.readLine();
		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); } 
}