LintCode - Knight Shortest Path

Given a knight in a chessboard (a binary matrix with 0as empty and 1as barrier) with asourceposition, find the shortest path to adestinationposition, return the length of the route. Return-1if knight can not reached.

Example

[[0,0,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return 2

[[0,1,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return 6

[[0,1,0],
 [0,0,1],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return -1

Analysis

The example shows that the knight doesn't go straight lines. It's like the Chinese chess. The idea is simple. Start the knight at the source position and list out all the possible valid moves (invalid if the move will make the knight be out of boundary or if it's a position that the knight has already been) until the destination is reach or the knight is out of moves. One nice way of implementation of possible moves is list out the x,y correlated deltas and loop over them with the source position.

  public int[] deltaX = new int[]{-2, -2, -1, -1, 1, 1, 2 ,2};
  public int[] deltaY = new int[]{-1, +1, -2, 2, -2, 2, -1 ,1};

  for (int i = 0; i < 8; i++){
      Point newPoint = new Point(point.x + deltaX[i], point.y + deltaY[i]);
  }

Another nice way to filter out the invalid moves and increase performance is make a position a barrier as soon as it is being added to the next possible moves.

grid[newPoint.x][newPoint.y] = true; //block it

Solution

    public int[] deltaX = new int[]{-2, -2, -1, -1, 1, 1, 2 ,2};
    public int[] deltaY = new int[]{-1, +1, -2, 2, -2, 2, -1 ,1};

    public int shortestPath(boolean[][] grid, Point source, Point destination) {
        Queue<Point> queue = new LinkedList<Point>();
        queue.offer(source);

        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                Point point = queue.poll();
                if (point.x == destination.x && point.y == destination.y) {
                    return count;
                } else {
                    for (int i = 0; i < 8; i++){
                        Point newPoint = new Point(point.x + deltaX[i], point.y + deltaY[i]);
                        if (inBound(grid, newPoint)) {
                            queue.offer(newPoint);
                            grid[newPoint.x][newPoint.y] = true; //block it
                        }
                    }    
                }
                size--;
            }
            count++;
        }

        return -1;
    }

    public boolean inBound(boolean[][] grid, Point p) {
        return p.x >= 0 && p.x < grid.length && p.y >= 0 && p.y < grid[0].length && !grid[p.x][p.y];
    }