1. 


/* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #439 (Knight Moves)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=380
*
* @author Dennis Wilfert
* @author Johann Studt
* @version 1.0, 06/22/2009
*
* Status : Accepted
* Runtime: 0.776
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

// Schachfeld
static int[][] field;
// Anzahl der benötigten Züge
static int moves;
public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder output = new StringBuilder();

// Eingabezeile
String line;

// Eingabezeile als char-Array
char[] input;

while(true){

// Zeile Auslesen
line = reader.readLine();
// Beenden wenn es keine Zeile mehr gibt
if(line==null)break;
// Zeile in char-Array umwandeln
input = line.toCharArray();

// Sind beide Koordinaten gleich, dann 0 ausgeben
if(input[0] == input[3] && input[1] == input[4]){
output.append("To get from ");
output.append(input[0]);
output.append(input[1]);
output.append(" to ");
output.append(input[3]);
output.append(input[4]);
output.append(" takes 0 knight moves.\n");

}
else{
// Neues Feld
field = new int[8][8];
// Züge auf 0 setzen
moves = 0;

// Anzahl der Züge bestimmen
coordinates(input[0]-97, input[1]-49, 0, input[3]-97, input[4]-49);

output.append("To get from ");
output.append(input[0]);
output.append(input[1]);
output.append(" to ");
output.append(input[3]);
output.append(input[4]);
output.append(" takes ");
output.append(moves);
output.append(" knight moves.\n");
}

}
System.out.print(output);


}

/*
* Anzahl der benötigten Züge rekursiv bestimmen
*/
static void coordinates(int x, int y, int n, int x2, int y2){
// Schauen ob die Koordinaten im gültigen bereich sind und ob im Feld nicht bereits ein niedrigerer Wert steht
if((x>=0 && x<8 && y>=0 && y<8) && (field[x][y]>n || field[x][y]==0)){
// Anzahl der Züge n an den Koordinaten eintragen
field[x][y]=n;
// Sind die Koordinaten gleich den Zielkoordinaten, dann n zurückgeben
if(x==x2 && y==y2)
moves = n;

// Alle möglichen Züge von den aktuellen Koordinaten durchlaufen
coordinates(x-1, y-2, n+1, x2, y2);
coordinates(x-1, y+2, n+1, x2, y2);
coordinates(x+1, y-2, n+1, x2, y2);
coordinates(x+1, y+2, n+1, x2, y2);
coordinates(x-2, y-1, n+1, x2, y2);
coordinates(x-2, y+1, n+1, x2, y2);
coordinates(x+2, y-1, n+1, x2, y2);
coordinates(x+2, y+1, n+1, x2, y2);
}

}

}


2.

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #439 Knight Moves
* Link: http://uva.onlinejudge.org/external/4/439.pdf
*
* @author Mohr
* @author Schirm
* @author Mathauser
* @version 1.0, 07/06/2009
*
* Status : Accepted
* Runtime: 1.892
*/

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

public static void main(String... args) throws Exception {

Scanner reader = new Scanner(System.in);
int[][] chess;
String line, field1, field2;
int startX, startY;
int endX, endY;

while (reader.hasNext()) {

chess = new int[8][8];
line = reader.nextLine();
field1 = line.split(" ")[0];
field2 = line.split(" ")[1];

startX = field1.charAt(0) - 'a';
startY = field1.charAt(1) - '1';

endX = field2.charAt(0) - 'a';
endY = field2.charAt(1) - '1';

ArrayList<ArrayList<Integer>> toDoList = new
ArrayList<ArrayList<Integer>>();
ArrayList<Integer> cords = new ArrayList<Integer>();
cords.add(startX);
cords.add(startY);
toDoList.add(cords);

while (!toDoList.isEmpty()) {
cords = toDoList.get(0);
int x = cords.get(0);
int y = cords.get(1);

int sum = chess[x][y] + 1;

if (x - 1 >= 0
&& y + 2 < 8
&& (sum < chess[x - 1][y + 2] || chess[x - 1][y + 2] == 0)
&& !(x - 1 == startX && y + 2 == startY)) {
chess[x - 1][y + 2] = sum;
cords = new ArrayList<Integer>();
cords.add(x - 1);
cords.add(y + 2);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

if (x + 1 < 8
&& y + 2 < 8
&& (sum < chess[x + 1][y + 2] || chess[x + 1][y + 2] == 0)
&& !(x + 1 == startX && y + 2 == startY)) {
chess[x + 1][y + 2] = sum;
cords = new ArrayList<Integer>();
cords.add(x + 1);
cords.add(y + 2);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

if (x - 1 >= 0
&& y - 2 >= 0
&& (sum < chess[x - 1][y - 2] || chess[x - 1][y - 2] == 0)
&& !(x - 1 == startX && y - 2 == startY)) {
chess[x - 1][y - 2] = sum;
cords = new ArrayList<Integer>();
cords.add(x - 1);
cords.add(y - 2);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

if (x + 1 < 8
&& y - 2 >= 0
&& (sum < chess[x + 1][y - 2] || chess[x + 1][y - 2] == 0)
&& !(x + 1 == startX && y - 2 == startY)) {
chess[x + 1][y - 2] = sum;
cords = new ArrayList<Integer>();
cords.add(x + 1);
cords.add(y - 2);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

if (x - 2 >= 0
&& y + 1 < 8
&& (sum < chess[x - 2][y + 1] || chess[x - 2][y + 1] == 0)
&& !(x - 2 == startX && y + 1 == startY)) {
chess[x - 2][y + 1] = sum;
cords = new ArrayList<Integer>();
cords.add(x - 2);
cords.add(y + 1);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

if (x + 2 < 8
&& y + 1 < 8
&& (sum < chess[x + 2][y + 1] || chess[x + 2][y + 1] == 0)
&& !(x + 2 == startX && y + 1 == startY)) {
chess[x + 2][y + 1] = sum;
cords = new ArrayList<Integer>();
cords.add(x + 2);
cords.add(y + 1);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

if (x - 2 >= 0
&& y - 1 >= 0
&& (sum < chess[x - 2][y - 1] || chess[x - 2][y - 1] == 0)
&& !(x - 2 == startX && y - 1 == startY)) {
chess[x - 2][y - 1] = sum;
cords = new ArrayList<Integer>();
cords.add(x - 2);
cords.add(y - 1);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

if (x + 2 < 8
&& y - 1 >= 0
&& (sum < chess[x + 2][y - 1] || chess[x + 2][y - 1] == 0)
&& !(x + 2 == startX && y - 1 == startY)) {
chess[x + 2][y - 1] = sum;
cords = new ArrayList<Integer>();
cords.add(x + 2);
cords.add(y - 1);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

toDoList.remove(0);
}

System.out.println("To get from " + field1 + " to " + field2
+ " takes " + chess[endX][endY]
+ " knight moves.");

}

}
}