1. 
package problemSetVolumes.volume004;

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10 
 * Problem: 439 - Knight Moves
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=380
 * 
 * @author Siegfried Ippisch
 * @version 1.0
 * 
 * Method : Floyd–Warshall algorithm
 * Status : Accepted
 * Runtime: 1.260
 */
public class KnightMoves {
	
	public static final int SIZE = 8*8;
	static int[][] adja = new int[SIZE][SIZE];
	
	private static void initField() {
		for(int i=0; i<SIZE; i++)
			Arrays.fill(adja[i], 1000);
		
		// Distance between same fields = 0
		for(int i=0; i<SIZE; i++)
			adja[i][i] = 0;
		
		// Distance to fields, where knight can jump = 1
		for(int x=0; x<8; x++)
			for(int y=0; y<8; y++){
				int index = x+8*y;
				adjaConnect(index, x+1, y+2);
				adjaConnect(index, x+2, y+1);
				adjaConnect(index, x-1, y+2);
				adjaConnect(index, x-2, y+1);
				adjaConnect(index, x+1, y-2);
				adjaConnect(index, x+2, y-1);
				adjaConnect(index, x-1, y-2);
				adjaConnect(index, x-2, y-1);
			}
	}
	
	private static void adjaConnect(int i, int x, int y){
		if(x>=0 && x<8 && y>=0 && y<8){
			int j = x+8*y;
			adja[i][j] = 1;
			adja[j][i] = 1;
		}
	}
	
	public static void floydWarshall(){
		for (int k = 0; k < SIZE; k++)
			for (int i = 0; i < SIZE; i++)
				for (int j = 0; j < SIZE; j++)
					adja[i][j] = Math.min(adja[i][j], adja[i][k] + adja[k][j]);
	}
	
	public static void main(String[] args) throws IOException{
		
		initField();
		floydWarshall();
		
		Scanner in = new Scanner(System.in);
		
		while(in.hasNext()){
			
			String s1 = in.next();
			String s2 = in.next();
			System.out.printf("To get from %s to %s takes %d knight moves.",s1,s2,
					adja[ s1.charAt(0)-'a' + (s1.charAt(1)-'1')*8 ]
						[ s2.charAt(0)-'a' + (s2.charAt(1)-'1')*8 ]);
			System.out.println();
		}
		
		in.close();
	}
	
}


2.

package acm_439_knight_moves;

/**
 * FWP, AusgewŠhlte Probleme aus dem ACM Programming Contest, SS10 
 * Problem: acm_439_knight_moves
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=380
 * 
 * @author Martin Lambeck
 * @version 1.0, 10.08.2010
 * 
 * Method : bfs
 * Status : Accepted
 * Runtime: 1.624
 */

import java.util.LinkedList;
import java.util.Scanner;

public class Main
{
	static Scanner sc = new Scanner(System.in);

	static int size = 8;

	//legal knight moves
	static int[][] move = new int[][]{
		{2, 1}, {2, -1},
		{1, 2}, {1, -2},
		{-1, 2}, {-1, -2},
		{-2, 1}, {-2, -1}};

	//chessboard
	static int[][] field = new int[size][size];


	public static void main(String... args)
	{
		while (testcase());
	}

	static void init()
	{
		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++)
				field[i][j] = -1;
	}

	static boolean testcase()
	{
		int xfrom, yfrom, xto, yto;
		String from, to;

		if (!sc.hasNext())
			return false;

		from = sc.next();
		to = sc.next();

		xfrom = from.getBytes()[0] - (int) 'a';
		yfrom = from.getBytes()[1] - (int) '1';
		xto = to.getBytes()[0] - (int) 'a';
		yto = to.getBytes()[1] - (int) '1';

		init(); //initial chessboard

		jump(xfrom, yfrom, xto, yto);

		System.out.printf("To get from %s to %s takes %d knight moves.%n", from, to, field[xto][yto]);

		return true;
	}

	//bfs
	static void jump (int fx, int fy, int tx, int ty)
	{
		int x, y;
		int step = 0;

		LinkedList<int[]> q = new LinkedList<int[]>();

		field[fx][fy] = 0; //start field

		if (fx == tx && fy == ty)
			return;
		
		q.add(new int[]{fx, fy}); //start field

		while (q.size() > 0)
		{
			step++;

			int neighbors = q.size();

			for (int j = 0; j < neighbors; j++)
			{
				int[] p = q.pollFirst();

				for (int i = 0; i < move.length; i++) //consider all legal knight moves
				{
					x = p[0] + move[i][0];
					y = p[1] + move[i][1];

					if (isValid(x, y) && (field[x][y] == -1)) //if valid field, and field unvisited
					{
						field[x][y] = step;
						q.add(new int[]{x, y});

						if (x == tx && y == ty) //if destination field
							return;
					}
				}
			}
		}	
	}

	//is this field inside the chessboard?
	static boolean isValid(int x, int y)
	{
		if ((x >= 0) && (x < size) && (y >= 0) && (y < size))
			return true;

		return false;
	}
}