Knight Shortest Path

题目 ：

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

说明

If the knight is at (x,y), he can get to the following positions in one step

(x + 1, y + 2)
(x + 1, y - 2)
(x - 1, y + 2)
(x - 1, y - 2)
(x + 2, y + 1)
(x + 2, y - 1)
(x - 2, y + 1)
(x - 2, y - 1)

样例：

[[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

代码实现：

 * Definition for a point.
 * public class Point {
 *     publoc int x, y;
 *     public Point() { x = 0; y = 0; }
 *     public Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    int n, m; // size of the chessboard
    //魔法数组
    int[] deltaX = {1, 1, 2, 2, -1, -1, -2, -2};
    int[] deltaY = {2, -2, 1, -1, 2, -2, 1, -1};
    /**
     * @param grid a chessboard included 0 (false) and 1 (true)
     * @param source, destination a point
     * @return the shortest path 
     */
    public int shortestPath(boolean[][] grid, Point source, Point destination) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }
        
        n = grid.length;
        m = grid[0].length;
        
        Queue<Point> queue = new LinkedList<>();
        queue.offer(source);
        grid[source.x][source.y] = true; 
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point point = queue.poll();
                if (point.x == destination.x && point.y == destination.y) {
                    return steps;
                }            
                for (int direction = 0; direction < 8; direction++) {
                    Point nextPoint = new Point(
                        point.x + deltaX[direction],
                        point.y + deltaY[direction]
                    );      
                    if (!inBound(nextPoint, grid)) {
                        continue;
                    }
                    if (grid[nextPoint.x][nextPoint.y] == false) {
                    queue.offer(nextPoint);
                    // 标记point不可到达
                    grid[nextPoint.x][nextPoint.y] = true;
                    }
                }
            }
            //遍 历完所有的下一跳节点，steps++
            steps++;
        }     
        return -1;
    }
    //判断是否在二维数组中
    private boolean inBound(Point point, boolean[][] grid) {
        return point.x >= 0 && point.x < grid.length && point.y >= 0
                  && point.y < grid[0].length; 
    }
}