FastSolution.java

import java.util.LinkedList;
import java.util.Queue;

import ga.rugal.lintcode.Point;

/**
 * https://www.lintcode.com/problem/knight-shortest-path/description
 *
 * @author rugal
 */
public class FastSolution {

  private static final int[][] N = new int[][]{{1, 2, 2, 1, -1, -2, -2, -1},
                                               {2, 1, -1, -2, -2, -1, 1, 2}};

  private boolean[][] grid;

  /**
   * @param grid:        a chessboard included 0 (false) and 1 (true)
   * @param source:      a point
   * @param destination: a point
   *
   * @return the shortest path
   */
  public int shortestPath(final boolean[][] grid, final Point source, final Point destination) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
      return -1;
    }
    if (source.x == destination.x && source.y == destination.y) {
      return 0;
    }
    this.grid = grid;
    final Queue<Point> q = new LinkedList<>();
    final boolean[][] visited = new boolean[grid.length][grid[0].length];
    q.offer(source);

    int dist = 0;

    while (!q.isEmpty()) {
      dist++;
      int size = q.size();
      for (int i = 0; i < size; i++) {
        final Point cur = q.poll();
        for (int k = 0; k < N[0].length; k++) {
          int nx = cur.x + N[0][k];
          int ny = cur.y + N[1][k];
          if (this.isValid(nx, ny) && !visited[nx][ny]) {
            if (nx == destination.x && ny == destination.y) {
              return dist;
            }
            q.offer(new Point(nx, ny));
            visited[nx][ny] = true;
          }
        }
      }
    }

    return -1;
  }

  private boolean isValid(final int x, final int y) {
    return 0 <= x && x < this.grid.length
           && 0 <= y && y < this.grid[0].length
           && !this.grid[x][y];
  }
}

SlowSolution.java

import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * @author rugal
 */
public class SlowSolution {

  private static final int[][] N = new int[][]{{1, 2, 2, 1, -1, -2, -2, -1},
                                               {2, 1, -1, -2, -2, -1, 1, 2}};

  private boolean[][] grid;

  /**
   * @param grid:        a chessboard included 0 (false) and 1 (true)
   * @param source:      a point
   * @param destination: a point
   *
   * @return the shortest path
   */
  public int shortestPath(final boolean[][] grid, final Point source, final Point destination) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
      return -1;
    }
    if (source.x == destination.x && source.y == destination.y) {
      return 0;
    }
    this.grid = grid;
    final Queue<Pair> queue = new LinkedList<>();
    final boolean[][] visited = new boolean[grid.length][grid[0].length];
    queue.offer(new Pair(source, 0));
    while (!queue.isEmpty()) {
      final Pair top = queue.poll();
      if (top.point.x == destination.x
          && top.point.y == destination.y) {
        return top.distance;
      }
      visited[top.point.x][top.point.y] = true;
      for (int i = 0; i < N[0].length; ++i) {
        final int x = N[0][i] + top.point.x;
        final int y = N[1][i] + top.point.y;
        if (this.isValid(x, y) && !visited[x][y]) {
          queue.offer(new Pair(new Point(x, y), top.distance + 1));
        }
      }
    }
    return -1;
  }

  private boolean isValid(final int x, final int y) {
    return 0 <= x && x < this.grid.length
           && 0 <= y && y < this.grid[0].length
           && !this.grid[x][y];
  }

  private class Pair {

    Point point;

    int distance;

    public Pair(Point point, int distance) {
      this.point = point;
      this.distance = distance;
    }
  }
}