import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Knight Moves * * We'll use a simple breadth-first search. * * @author vanb */ public class knightmoves_vanb { public Scanner sc; public PrintStream ps; /** * A State of the BFS. * It'll include the (i,j) position of the knight, * and the number of moves so far. * * @author vanb */ public class State { /** i,j=position, distance=# moves */ public int i, j, distance; /** * Create a State. * * @param i Row * @param j Column * @param distance Number of MOves */ public State( int i, int j, int distance ) { this.i = i; this.j = j; this.distance = distance; } } /** di[] and dj[] describe the ways a knight can move. */ public static final int di[] = { 1, 2, 2, 1, -1, -2, -2, -1 }; public static final int dj[] = { 2, 1, -1, -2, 2, 1, -1, -2 }; /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); ps = System.out; // Read in the limits int n = sc.nextInt(); int m = sc.nextInt(); // Read in the board char board[][] = new char[n][]; for( int i=0; i q = new LinkedList(); // Starting state of the BFS is the starting coords, 0 moves q.add( new State( starti, startj, 0 ) ); while( !q.isEmpty() ) { State s = q.pollFirst(); // Have we reached the target? if( board[s.i][s.j]=='X' ) { answer = s.distance; break; } // Go through all of the possible knight moves for( int d=0; d=0 && ii=0 && jj